- #include <stdio.h>
- #define N 200000001
- unsigned int f[(N>>5)+5];
- unsigned int p[N/10];
- int m;
- void set(int x)
- {
- f[x>>5] |= 1<<(x&0x1F);
- }
- int get(int x)
- {
- return f[x>>5] & (1<<(x&0x1F));
- }
- int prime()
- {
- long long i;
- long long j;
- m = 0;
- set(0);
- set(1);
- for (i=4; i<N; i+=2)
- {
- set(i);
- }
- for (i=3; i*i<N; i+=2)
- {
- if (!get(i))
- {
- for (j=i*i; j<N; j+=i)
- set(j);
- }
- }
- for (i=2; i<N; ++i)
- if (!get(i))
- p[m++] = i;
- return m;
- }
- int isPrime(unsigned int x)
- {
- if (x < N)
- {
- return !get(x);
- }
- int i;
- for (i=0; p[i]*p[i]<=x; ++i)
- {
- if (x%p[i] == 0)
- return 0;
- }
- return 1;
- }
- int main(void) {
- prime();
- printf("There are %d primes less than %d.\\n", m, N);
- printf("Last prime: %d\\n", p[m-1]);
- int n = -1u>>1;
- printf("%d %s prime.\\n", n, isPrime(n)?"is":"is not");
- n = 1234567;
- printf("%d %s prime.\\n", n, isPrime(n)?"is":"is not");
- printf("primes less than 500:\\n");
- int i;
- for (i=0; p[i]<500; ++i)
- {
- printf("%d ", p[i]);
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/0212201411141.html
来源: http://www.codesnippet.cn/detail/0212201411141.html