这是找到从1到n的所有质数的最快算法(在我的电脑上，它只花了0.004秒就找到了从1到1000000的所有质数)。

#include <iostream>
#include <fstream>

using namespace std;

double FindPrime(bool* array, int size){
clock_t start;
double runtime;
for (int i = 2; i < size; i++)
    array[i] = true;
start = clock();
for (int i = 2; i <= size; i++)
    if (array[i])
        for (int j = 2 * i; j < size; j += i)
            array[j] = false;
runtime = (double)(clock() - start) / CLOCKS_PER_SEC;
return runtime;
}


int main() {
ofstream fout("prime.txt");
int n = 0;
cout << "Enter the upper limit of prime numbers searching algorithm:";
cin >> n;
bool* array = new bool[n + 1];
double duration = FindPrime(array, n + 1);
printf("\n%f seconds.\n", duration);
for (int i = 2; i <= n; i++)
    if (array[i])
        fout << i << endl;
fout.close();

return 0;
}

一个非常快速的Atkin Sieve的实现是Dan Bernstein的primegen。这个筛子比埃拉托色尼的筛子更有效率。他的页面有一些基准测试信息。

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

寻找因素的解决方案:

def divisors(integer):
    result = set()
    i = 2
    j = integer/2
    while(i <= j):
        if integer % i == 0:
            result.add(i)
            #it dont need to 
            result.add(integer//i)
        i += 1
        j = integer//i
    if len(result) > 0:
        return f"not  prime {sorted(result)}"
    else:
        return f"{integer} is prime"

—测试---- 导入的时间

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

——0.06314539909362793秒——

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

——1.5997519493103027秒——

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

——0.0秒——

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

——0.0秒——

下面的代码:

def divs(integer):
    result = set()
    i = 2
    j = integer / 2
    loops = 0
    while (i <= j):
        if integer % i == 0:
            print(f"loops:{loops}")
            return f"{integer} is not a prime"
        i += 1
        j = integer // i
        loops += 1
    print(f"loops:{loops}")
    
    return f"{integer} is prime"

——测试——

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

——0.0秒——

I know it's somewhat later, but this could be useful to people arriving here from searches. Anyway, here's some JavaScript that relies on the fact that only prime factors need to be tested, so the earlier primes generated by the code are re-used as test factors for later ones. Of course, all even and mod 5 values are filtered out first. The result will be in the array P, and this code can crunch 10 million primes in under 1.5 seconds on an i7 PC (or 100 million in about 20). Rewritten in C it should be very fast.

var P = [1, 2], j, k, l = 3

for (k = 3 ; k < 10000000 ; k += 2)
{
  loop: if (++l < 5)
  {
    for (j = 2 ; P[j] <= Math.sqrt(k) ; ++j)
      if (k % P[j] == 0) break loop

    P[P.length] = k
  }
  else l = 0
}

这是找到从1到n的所有质数的最快算法(在我的电脑上，它只花了0.004秒就找到了从1到1000000的所有质数)。

#include <iostream>
#include <fstream>

using namespace std;

double FindPrime(bool* array, int size){
clock_t start;
double runtime;
for (int i = 2; i < size; i++)
    array[i] = true;
start = clock();
for (int i = 2; i <= size; i++)
    if (array[i])
        for (int j = 2 * i; j < size; j += i)
            array[j] = false;
runtime = (double)(clock() - start) / CLOCKS_PER_SEC;
return runtime;
}


int main() {
ofstream fout("prime.txt");
int n = 0;
cout << "Enter the upper limit of prime numbers searching algorithm:";
cin >> n;
bool* array = new bool[n + 1];
double duration = FindPrime(array, n + 1);
printf("\n%f seconds.\n", duration);
for (int i = 2; i <= n; i++)
    if (array[i])
        fout << i << endl;
fout.close();

return 0;
}