找到素数问题 两个素数之和必须是素数

#include

#include

#define n 20

int pnumber(int k)

int m=2;

while(m<=(int)sqrt(k) &k%m!=0)m++;if(m>(int)sqrt(k))return 1;

return 0;

int backtrack(int n,int a)int i,j;

for(i=1;i<=n;i++)

for(j=0;j=n)

a[n]=i;

return 1;

if( n==0 ||n>0&&na[n]=i;

if(backtrack(n+1,a))

return 1;

return 0;

main()

int a[n];

int i;

if(!backtrack(0,a))

printf("找不到这样的安排！ ");

elsefor(i=0;iprintf("%d ",a[i]);

printf("");

素环问题ZJU1457，一种典型的回溯算法。

我在硬盘上找到了当年的**; 可以输入20个，但是组合太多，屏幕马虎，CPU还行吗？

这个问题必须用奇数和偶数来修剪，否则会超时！

#include

int a[50],b[50],p[50],n;

void ring(int w)

int i;

if(w==n)

if(p[a[n-1]+1]==1)

printf("1");

for(i=1;iprintf("");

elsefor(i=a[w-1]%2+1;i<=n;i+=2)if(b[i]==0 &&p[i+a[w-1]]==1)a[w]=i;

b[i]=1;

ring(w+1);

b[i]=0;

int main()

int i,j,d,k=1,flag;

for(i=3;i<50;i+=2)

d=i/3;

flag=1;

for(j=3;j<=d;j+=2)

if(i%j==0)

flag=0;

break;

else d=i/j;

p[i]=flag;

printf("case %d:",k++)if(n%2==0)

for(i=2;i<=n;i++)b[i]=0;

a[0]=1;

b[1]=1;

ring(1);

printf("");

return 0;

将 20 个数字排成一排，使两个相邻数字的总和是一个质数，第一个和最后一个数字的总和也是一个质数。 以编程方式打印出一种排列方式。

根据素数的含义，最小的素数是2,2和其他素数之和可以是素数，如2+3=5，也可以是合数，如2+7=9

除 2 外，任意两个素数之和都是大于 2 的偶数，即合数，所以两个素数之和一定是质数是错误的

所以答案是：错的

素数（也称为素数）。

1.只有两个因数（1 和自身）的自然数称为质数。 也可以说素数本身只有 1 和 2 除数。

2.素数是一个整指数，除了作为自身和 1 的乘积外，不能表示为任何一个。

其他两个整数的乘积。

如果是 if（n%d==0），则它不是质数，因为除法本身的余数为 0

更严格地说，小于根数n应改为小于或等于根数n，否则结论不满足素数的平方。

反之，n不是素数，那么n可以分解为两个小于n的正整数的乘积，让。

n=ab.在这里，我们可以认为 a 和 b 都是质数。 事实上，如果a，b不都是素数，例如，a前面没有，那么，根据算术的基本定理，a可以分为几个素数的幂的乘积（例如。

60=（2 2）*3*5 等），a 的质因数也是 n 的质因数，它能被 n（n n） 整除，不能被任何小于棚子宽度等于根数 n 的质数整除。

根据问题，n不能被任何小于或等于根数n的素数整除，并且有n=ab，所以只有a>根n，b>根数n，在这种情况下n=ab>n，是矛盾的，所以假设不成立，所以n是素数。

首先，明确程序的目标是找到质数：

素数的概念是它们不能被 1 和它们本身以外的数字整除;

那么外圈显然是遍历 2-lim 数的质数;

内部循环是确定 2 lim 范围内的 i 是否可以被 2 到 i-1 的数字整除;

当它可以被分割时，它会跳出内循环;

如果（j>=i）实际上可以改为j==i，即j在内循环中累积到i-1时没有找到能被i整除的数，所以它遵循++，但是这时j变得和i一样大，不满足内循环的条件，所以内循环结束， 未找到可分割性，输入 if（j>=i） 判断;

而j>=i其实是一个简单的滤波器，防止在其他可整除的情况下跳出来，不是素数，所以不需要记录;