我必须找到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)表亲质数是(3，7)，(7，11)，(13，17)，(19，23)，(37，41)，(43，47)，(67，71)，(79，83)。
SO 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;
}
我使用了无符号的长线，这样我就可以用这个程序来寻找大的数字。
编辑主函数
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;
}
这个主函数给出了孪生质数和表兄质数。但我想找到这两个数的共同数。这让我很困惑。我不知道该怎么做才能找到公有数。
一个简单的解决方案(需要额外的内存--可能会被优化)是建立双胞胎和表兄弟的列表，并将这两个列表相交。
例子:
#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: 8
你可以通过记账来实现，同时每个质数只计算一次。
这是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)
{
Console.Write($"{prev} ");
count++;
}
primes.Add(i);
wasTwin = isTwin; wasCousin = isCousin; prev = i;
}
}
Console.WriteLine($"\nNumbers:{count}");
}