codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <stdio.h> #include <math.h> #include <assert.h> #define MAX_N 50000 unsigned int primes[1 + MAX_N/64] = {0}; void fetch_n(int n, int *pi, int *pb) { int index = n/2 - 1; *pi = index / 32; *pb = index % 32; assert(*pi <= MAX_N/64); } void set_n(int n) { if(n >= MAX_N) return; assert(n % 2); int index, bitno; fetch_n(n, &index, &bitno); primes[index] |= (1U << bitno); } int get_n(int n) { if(n >= MAX_N) return 0; assert(n % 2); int index, bitno; fetch_n(n, &index, &bitno); return ( primes[index] & (1U << bitno) ); } int main() { int i = 0, j = 3; primes[i++] = 2; printf("%d\n", 2); set_n(3); printf("%d\n", 3); for(j = 5; j < MAX_N; j += 2) { int upto = (int)( sqrt(j) ); int k = 0; for(k = 3; k <= upto; k += 2) { if( get_n(k) && (j % k == 0) ){ k = -1; break; } } if(-1 != k) { set_n(j); printf("%d\n", j); } } return 0; }
Private
[
?
]
Run code
Submit