
Originally Posted by
Bulat Ziganshin
i wonder why log(n) here? i just enumerate all odd numbers less than sqrt(n). with about 10 seconds for one N in the worst case and 0.01 seconds for 32-bit N, this algo is fast enough for my needs
a big number n has a probability of (1/logn) to become a prime, so you are expected to test 0.5logn numbers before you find it. but i'm not sure that test a len=log(n) sequence numbers need O(log(n)*sqrt(n)) because not all numbers need sqrt(n) to test.
add here is a even faster implement, skipping multiple of 2, 3, 5:
Code:
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main(int argc, char** argv) {
unsigned long long n;
unsigned long long m;
unsigned long long i;
int is_prime = 0;
sscanf(argv[1], "%llu", &n);
if(n <= 2) return printf("%d is a prime.\n", 2), 0;
if(n <= 3) return printf("%d is a prime.\n", 3), 0;
if(n <= 5) return printf("%d is a prime.\n", 5), 0;
if(n <= 7) return printf("%d is a prime.\n", 7), 0;
if(n <= 11) return printf("%d is a prime.\n", 11), 0;
if(n <= 13) return printf("%d is a prime.\n", 13), 0;
if(n <= 17) return printf("%d is a prime.\n", 17), 0;
if(n <= 19) return printf("%d is a prime.\n", 19), 0;
if(n <= 23) return printf("%d is a prime.\n", 23), 0;
if(n <= 29) return printf("%d is a prime.\n", 29), 0;
n += (n % 2 == 0);
while(!is_prime) {
if(n % 3 == 0 || n % 17 == 0) {n += 2; continue;}
if(n % 5 == 0 || n % 19 == 0) {n += 2; continue;}
if(n % 7 == 0 || n % 23 == 0) {n += 2; continue;}
if(n % 11 == 0 || n % 29 == 0) {n += 2; continue;}
if(n % 13 == 0) {n += 2; continue;}
m = sqrt(n) + 10;
is_prime = 1;
for(i = 30; i < m; i += 30) {
if( n % (i + 1) == 0 || n % (i + 7) == 0 || n % (i + 11) == 0 ||
n % (i + 13) == 0 || n % (i + 17) == 0 ||
n % (i + 19) == 0 || n % (i + 23) == 0 || n % (i + 29) == 0) {
is_prime = 0;
break;
}
}
if(is_prime) {
printf("%llu is a prime.", n);
return 0;
}
n += 2;
}
return 0;
}