超长代码——也不怪我没有注释吧
- Miller_rabin算法
#include <iostream>
#include <cstdio>
using namespace std;
int ksm(int x, int y, int z)
{
if (! y) return 1;
int ans = ksm(x, y >> 1, z);
ans = 1LL * ans * ans % z;
if (y & 1) ans = 1LL * ans * x % z;
return ans;
}
int list[10] = {2, 3, 5, 7, 13, 23, 59, 61};
bool miller_rabin(long long n,long long a)
{
long long d = n -1, r = 0;
while((d & 1) == 0)
{
d >>= 1;
r ++;
}
long long x = ksm(a, d, n);
if(x== 1)
{
return true;
}
for(int i = 0; i <r ; i ++)
{
if(x == n - 1)
{
return true;
}
x = 1LL * x * x % n;
}
return false;
}
bool isprime(long long n )
{
if(n < 2) return false;
for(int a= 0;a< 8; a ++)
{
if(n == list[a])
{
return true;
}
if(n % list[a] == 0)
{
return false;
}
if(! miller_rabin(n, list[a]))
{
return false;
}
}
return true;
}
int lst = 0;
bool vis[1000010];
int prime[1000010];
void ycl()
{
for (int i = 2; i <= 1000000; i ++)
if (isprime(i)) prime[++ lst] = i, vis[i] = true;
}
inline bool find(int x)
{
return vis[x];
}
int main()
{
ycl(); // -- init -- 代表ycl,是同一个意思
int n;
while (scanf("%d", &n) == 1 && n)
{
for (int j = 1; j <= lst; j ++)
{
if (find(n - prime[j]))
{
printf ("%d = %d + %d\n", n, prime[j], n - prime[j]);
goto nxt;
}
}
nxt:;
}
return 0;
}
- 埃式筛法
(代码待补)
- 欧拉筛法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int lst;
int prime[100000007];
bool not_prime[100000007];
bool prime3383()
{
for(int a=2; a<=1000000; a++)
{
if(!not_prime[a]) prime[++lst]=a;
for(int b=1; b<=lst; b++)
{
int x=prime[b]*a;
if(x>1000000) break;
not_prime[x]=true;
if(a%prime[b]==0) break;
}
}
return true;
}
void init_PrimeLs()
{
prime3383();
}
int main()
{
init_PrimeLs();
int n;
while (scanf ("%d", &n) == 1 && n)
{
bool flag = false;
for (int i = 1; i <= lst; i ++)
if (! not_prime[n - prime[i]])
{
printf("%d = %d + %d\n", n, prime[i], n - prime[i]);;
flag = true;
break;
}
if (! flag)
puts("Goldbach's conjecture is wrong.");
}
return 0;
}
- 打表(这个请您自己来填吧)
(等待填写,实际上打一个文件就可以了)