Welcher ist der schnellste Algorithmus zur Auffindung von Primzahlen?

Question

Welcher ist der schnellste Algorithmus, um Primzahlen mit C++ zu finden? Ich habe das Siebverfahren verwendet, aber ich möchte immer noch, dass es schneller wird!

Answer 1

Ich habe es heute in C geschrieben, mit tcc kompiliert, während der Vorbereitung auf Wettbewerbsprüfungen vor einigen Jahren herausgefunden. Ich weiß nicht, ob es bereits jemand geschrieben hat. Es ist wirklich schnell (aber Sie sollten entscheiden, ob es schnell ist oder nicht). Es hat ein oder zwei Minuten gedauert, um herauszufinden, dass es zwischen 10 und 1.000.000.000 auf einem i7-Prozessor mit durchschnittlich 32 % CPU-Auslastung etwa 100.004 Primzahlen gibt. Wie Sie wissen, können nur diejenigen Primzahlen sein, die als letzte Ziffer entweder 1, 3, 7 oder 9 haben, und um zu überprüfen, ob diese Zahl eine Primzahl ist oder nicht, müssen Sie diese Zahl nur durch zuvor gefundene Primzahlen dividieren. nehmen Sie also zuerst eine Gruppe von vier Zahlen = {1,3,7,9}, testen Sie es, indem Sie es durch bekannte Primzahlen teilen, wenn der Rest nicht null ist, ist die Zahl prim, fügen Sie sie zum Primzahlen-Array hinzu. fügen Sie dann 10 zur Gruppe hinzu, sodass sie {11,13,17,19} wird, und wiederholen Sie den Vorgang.

#include 
int main() {
    int nums[4]={1,3,7,9};
    int primes[100000];
    primes[0]=2;
    primes[1]=3;
    primes[2]=5;
    primes[3]=7;
    int found = 4;
    int got = 1;
    int m=0;
    int bis = 1000000;
    for(int i=0;i

Answer 2

Ich habe kürzlich diesen Code geschrieben, um die Summe der Zahlen zu finden. Es kann einfach modifiziert werden, um stattdessen festzustellen, ob eine Zahl eine Primzahl ist oder nicht. Leistungsindikatoren stehen oben im Code.

// erstellt auf core-i2 e8400
// Benchmark von PowerShell
// Measure-Command { ExeName.exe }
// Tage              : 0
// Stunden           : 0
// Minuten           : 0
// Sekunden          : 23
// Millisekunden     : 516
// Ticks             : 235162598
// Gesamttage        : 0,00027217893287037
// Gesamtstunden     : 0,00653229438888889
// Gesamtminuten     : 0,391937663333333
// Gesamtsekunden    : 23,5162598
// Gesamtmillisekunden : 23516,2598
// erstellt mit dem neuesten MSVC
// cl /EHsc /std:c++latest main.cpp /O2 /fp:fast /Qpar

#include 
#include 
#include 

inline auto prime = [](std::uint64_t I, std::vector &cache) -> std::uint64_t {
    std::uint64_t root{static_cast(std::sqrtl(I))};
    for (std::size_t i{}; cache[i] <= root; ++i)
        if (I % cache[i] == 0)
            return 0;

    cache.push_back(I);
    return I;
};

inline auto prime_sum = [](std::uint64_t S) -> std::uint64_t {
    std::uint64_t R{5};
    std::vector cache;
    cache.reserve(S / 16);
    cache.push_back(3);

    for (std::uint64_t I{5}; I <= S; I += 8)
    {
        std::uint64_t U{I % 3};
        if (U != 0)
            R += prime(I, cache);
        if (U != 1)
            R += prime(I + 2, cache);
        if (U != 2)
            R += prime(I + 4, cache);
        R += prime(I + 6, cache);
    }
    return R;
};

int main()
{
    std::cout << prime_sum(63210123);
}

Answer 3

Ich verwende immer diese Methode zur Berechnung von Primzahlen mit dem Siebalgorithmus.

void primelist()
 {
   for(int i = 4; i < pr; i += 2) mark[ i ] = false;
   for(int i = 3; i < pr; i += 2) mark[ i ] = true; mark[ 2 ] = true;
   for(int i = 3, sq = sqrt( pr ); i < sq; i += 2)
       if(mark[ i ])
          for(int j = i << 1; j < pr; j += i) mark[ j ] = false;
  prime[ 0 ] = 2; ind = 1;
  for(int i = 3; i < pr; i += 2)
    if(mark[ i ]) ind++; printf("%d\n", ind);
 }

Answer 4

Lösung zur Findung der Faktoren:

def divisors(integer):
    result = set()
    i = 2
    j = integer/2
    while(i <= j):
        if integer % i == 0:
            result.add(i)
            #es ist nicht erforderlich 
            result.add(integer//i)
        i += 1
        j = integer//i
    if len(result) > 0:
        return f"keine Primzahl {sorted(result)}"
    else:
        return f"{integer} ist eine Primzahl"

--- Tests ---- import time

start_time = time.time()
print(divisors(180180180180))
print("--- %s Sekunden ---" % (time.time() - start_time))

--- 0.06314539909362793 Sekunden ---

start_time = time.time()
print(divs(180180180180180))
print("--- %s Sekunden ---" % (time.time() - start_time))

--- 1.5997519493103027 Sekunden ---

start_time = time.time()
print(divisors(1827))
print("--- %s Sekunden ---" % (time.time() - start_time))

--- 0.0 Sekunden ---

start_time = time.time()
print(divisors(104729))
print("--- %s Sekunden ---" % (time.time() - start_time))

--- 0.0 Sekunden ---

mit diesem Code:

def divs(integer):
    result = set()
    i = 2
    j = integer / 2
    loops = 0
    while (i <= j):
        if integer % i == 0:
            print(f"Schleifen:{loops}")
            return f"{integer} ist keine Primzahl"
        i += 1
        j = integer // i
        loops += 1
    print(f"Schleifen:{loops}")

    return f"{integer} ist eine Primzahl"

--- Tests ---

start_time = time.time()
print(divs(180180180180180180180180))
print("--- %s Sekunden ---" % (time.time() - start_time))

--- 0.0 Sekunden ---

Answer 5

#include
main()
{
    long long unsigned x,y,b,z,e,r,c;
    scanf("%llu",&x);
    if(x<2)return 0;
    scanf("%llu",&y);
    if(y0)z=3;
        }
        if(e==0)
        {
            printf("|%llu",z);
            r+=1;
        }
    }
    printf("|\n%llu Ausgaben...\n",r);
    scanf("%llu",&r);
}