如何找到孪生素数和表亲素数的素数？
如何找到孪生素数和表亲素数的素数？
提问于 2020-06-11 08:04:32
我必须找到一对素数成员和表亲素数成员的1到100之间的素数。
例如:7是孪生素数的成员，也是表亲素数的成员。
另外，我还得找出有多少这样的数字在1到100之间。
样本输入和输出：
start = 1
end = 100产出:7 11 13 17 19 41 43 71
说明:1至100中的孪生素数是(3，5)，(5，7)，(11，13)，(17，19)，(29，31)，(41，43)，(59，61)，(71，73)表亲素数在1到100中是(3，7)，(7，11)，(13，17)，(19，23)，(37，41)，(43，47)，(67，71)，(79，83)。
因此，7，11，13，17，19，41，43，71数字都是孪生素数和表亲素数。
到目前为止，我已经尝试过：
为了检查双胞胎数字和表亲数字，我做了这个循环。
for(i = start; i < end; i++)
{
if(isPrime(i) && isPrime(i + 2))
{
if(isPrime(i+4) || isPrime(i+2+4))
{
count++;
printf("%d %d %d %d\n",i, i+2, i+4, i+6);
}
i++;
}
}
printf("\n");但这并没有给我正确的结果。
要改变什么才能让它发挥作用？
完整的代码如下：
int isPrime(unsigned long number)
{
int i, nb, count, test,limit;
test = count = 0;
nb = number;
limit = sqrt(nb) + 1;
if(nb == 1)
{
return 0;
}
if(nb == 2)
{
return 1;
}
if (nb % 2 == 0)
test = 1;
else{
for (i = 3 ; i < limit && ! test; i+=2, count++)
if (nb % i == 0)
test = 1;
}
if (!test)
return 1;
else
return 0;
}
int main()
{
int start, end;
printf("Enter start: ");
scanf("%d", &start);
printf("Enter end: ");
scanf("%d", &end);
int count = 0;
int count2 = 0;
unsigned long i;
for(i = start; i < end; i++)
{
if(isPrime(i) && isPrime(i + 2))
{
if(isPrime(i+4) || isPrime(i+2+4))
{
count++;
printf("%d %d %d %d\n",i, i+2, i+4, i+6);
}
i++;
//count++;
}
}
printf("\n");
printf("The number: %d",count);
return 0;
}我使用了未签名的long，以便以后可以使用这个程序查找大量的数字。
编辑主函数
int main()
{
int start, end;
printf("Enter start: ");
scanf("%d", &start);
printf("Enter end: ");
scanf("%d", &end);
int count = 0;
int count2 = 0;
unsigned long i;
for(i = start; i < end; i++)
{
if(isPrime(i) && isPrime(i + 2))
{
printf("[ %lu , %lu ]\n", i, i+2);
i++;
count++;
}
}
for(i = start; i < end; i++)
{
if(isPrime(i) && isPrime(i + 4))
{
printf("[ %lu , %lu ]\n", i, i+4);
i++;
count2++;
}
}
printf("The number of twins: %d",count);
printf("The number of cousins: %d",count2);
return 0;
}这个主要功能给出了孪生素数和表亲素数。但我想找出这两个人的共同数字。这让我有点困惑。我不知道该怎么办才能找到通用号码。
回答 2
Stack Overflow用户
回答已采纳
发布于 2020-06-11 09:37:59
一个简单的解决方案(需要额外的内存--可能需要优化)是构建双胞胎和堂兄弟的列表，并将这两个列表相交。
示例：
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <errno.h>
int isPrime(unsigned long number)
{
int i, nb, count, test,limit;
test = count = 0;
nb = number;
limit = sqrt(nb) + 1;
if(nb == 1)
{
return 0;
}
if(nb == 2)
{
return 1;
}
if (nb % 2 == 0)
test = 1;
else{
for (i = 3 ; i < limit && ! test; i+=2, count++)
if (nb % i == 0)
test = 1;
}
if (!test)
return 1;
else
return 0;
}
int main()
{
unsigned long start, end;
printf("Enter start: ");
scanf("%lu", &start);
printf("Enter end: ");
scanf("%lu", &end);
int count = 0;
int count2 = 0;
unsigned long i;
unsigned long j;
unsigned long *tl;
unsigned int tcount = 0;
unsigned long *cl;
unsigned int ccount = 0;
int found;
unsigned long int count3;
tl = malloc((end - start) * sizeof(unsigned long));
if (tl == NULL)
{
perror("malloc");
return 1;
}
cl = malloc((end - start) * sizeof(unsigned long));
if (cl == NULL)
{
perror("malloc");
return 1;
}
for(i = start; i < end; i++)
{
if(isPrime(i) && isPrime(i + 2))
{
printf("twin: \t[ %lu , %lu ]\n", i, i+2);
tl[tcount]=i;
tcount++;
tl[tcount]=i+2;
tcount++;
i++;
count++;
}
if(isPrime(i) && isPrime(i + 4))
{
printf("cousin: [ %lu , %lu ]\n", i, i+4);
cl[ccount]=i;
ccount++;
cl[ccount]=i+4;
ccount++;
i++;
count2++;
}
}
printf("The number of twins: %d\n",count);
printf("The number of cousins: %d\n",count2);
printf("List of common twins and cousins:\n");
count3 = 0;
for (i=0; i < tcount; i++)
{
found = 0;
for (j=0; j < ccount; j++)
{
if (tl[i] == cl[j])
found = 1;
}
if (found == 1)
{
count3++;
printf("%lu ",tl[i]);
}
}
printf("\n");
printf("The number of twins and cousins: %lu\n",count3);
return 0;
}处决：
$ ./ptc2
Enter start: 2
Enter end: 100
twin: [ 3 , 5 ]
twin: [ 5 , 7 ]
cousin: [ 7 , 11 ]
twin: [ 11 , 13 ]
cousin: [ 13 , 17 ]
twin: [ 17 , 19 ]
cousin: [ 19 , 23 ]
twin: [ 29 , 31 ]
cousin: [ 37 , 41 ]
twin: [ 41 , 43 ]
cousin: [ 43 , 47 ]
twin: [ 59 , 61 ]
cousin: [ 67 , 71 ]
twin: [ 71 , 73 ]
cousin: [ 79 , 83 ]
cousin: [ 97 , 101 ]
The number of twins: 8
The number of cousins: 8
List of common twins and cousins:
7 11 13 17 19 41 43 71
The number of twins and cousins: 8Stack Overflow用户
发布于 2020-06-11 11:13:16
有了一点簿记，你就可以做到这一点，而只计算每一个质数一次。
这是C#，但是你会想到：
static void CousinAndTwinPrimesUpTo(ulong max)
{
int count = 0;
List<ulong> primes = new List<ulong>();
ulong prev = 0; bool wasTwin = false; bool wasCousin = false;
for (ulong i = 3; i < max; i += 2)
{
bool isPrime = true;
foreach (var p in primes)
{
if (i % p == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
bool isTwin = i - 2 == prev;
bool isCousin = i - 4 == prev;
if (isTwin && wasCousin || isCousin && wasTwin)
{
count++;
}
primes.Add(i);
wasTwin = isTwin; wasCousin = isCousin; prev = i;
}
}
Console.WriteLine($"\nNumbers:{count}");
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62319755
复制相关文章
相似问题
腾讯云开发者
