艾拉托斯散筛法

艾拉托斯散筛法

这个算法可以求素数。我们在《信息安全数学基础》里学过。

附一道模板题。

hduoj_1397

#include <stdio.h>int isPrime[32768];void prime()
{int i, j;for (i = 1; i < 32768; i++)isPrime[i] = 1;for (i = 2; i < 32768; i++){if (isPrime[i]){for (j = i*i; j < 32768; j += i)isPrime[j] = 0;}}
}int main()
{int n;int i;int cnt;prime();while (1){scanf("%d", &n);if (!n)break;cnt = 0;for (i = 2; i <= n / 2; i++){if (isPrime[i] && isPrime[n - i])cnt++;}printf("%dn", cnt);}return 0;
}

poj_3518

#include <stdio.h>
#define max 1299710
int isPrime[max];void prime()
{long long i, j;for (i = 1; i < max; i++)isPrime[i] = 1;for (i = 2; i < max; i++){if (isPrime[i]){for (j = i*i; j < max; j += i)isPrime[j] = 0;}}
}int main()
{int n;int l, r;prime();while (1){scanf("%d", &n);if (!n)break;if (isPrime[n])printf("0n");else{l = n;while (!isPrime[l])l--;r = n;while (!isPrime[r])r++;printf("%dn", r - l);}}
}