寻找最大的双素数
我正在尝试创建一个c程序，它提示用户输入，然后在这个数字中找到最大的孪生素数。然后这个程序不断循环，一次又一次地提示用户输入，并找到最大的孪生质数，直到用户进入-1，之后它就终止了。我写下了基本代码，但在使用某些数字(例如20和65 )时，我还能够使它连续循环。我不知道我的代码有什么问题。
我似乎也有另一个问题。对于20，数值显示(15,17)而不是(17,19)。显然，逻辑是错误的，但我也不确定具体在哪里。
这是我的密码：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include<conio.h>
int prime(int x)
{
int i,numroot;
numroot=sqrt(x);
for(i=2;i<=numroot;i++)
if(x%i==0){
return(0);
}
return(1);
}
int main()
{
double N;
printf("This program prints out all the possible twin primes until a specific number which...\nyou can choose!");
printf("\nA note of caution: Although this program accepts decimals, the value entered must be between 5 and 10^9,inclusive of the 2 numbers.");
printf("\nKey in -1 to exit.");
printf("\nEnter N value upto which twin primes ought to be calculated until: ");
scanf("%lf",&N);
while (N!=-1) {
if (N<5 || N>pow(10,9)) {
printf("\nNumber not in the valid range was inputted. \nPlease reenter the value: ");
scanf("%lf",&N);
}
else {
int n;
n=floor(N);
int prime(int x);
int f,originalval;
originalval=N;
f=prime(n);
while(f==0){//Calculates for largest prime number below user input
n--;
f=prime(n);
}
int smallint=n-2;
while(prime(smallint)==1){
n--;
f=prime(n);
while(f==0){
n--;
f=prime(n);
}
int smallint=n-2;
}
printf("The largest twin prime pair not above %d is (%d,%d)",originalval,smallint,n);
printf("\nPlease re-enter the value:");
scanf("%lf",&N);
}
}
printf("\nProgram successfully terminated.");
return 0;
}回答 2
Stack Overflow用户
发布于 2015-08-05 05:00:20
我们应该使这两个数字都是素数。差异之间是2。众所周知，第一个孪生质数是(3,5)。我还没有找到我所期望的公式。所以，我用迭代来解决问题。如果你仔细看代码，你就能理解。
#include <stdio.h>
#include <math.h>
int twinPrime(int m);
int IsPrime(unsigned int number);
int main()
{
double N;
int floored;
int prime;
printf("This program prints out all the possible twin primes"
"until a specific number which...\nyou can choose!");
printf("\nA note of caution: Although this program accepts decimals, "
"the value entered must be between 5 and 10^9,inclusive of the 2 numbers.");
printf("\nKey in -1 to exit.");
printf("\nEnter N value upto which twin primes ought to be calculated until: ");
scanf("%lf",&N);
while (N != -1)
{
if (N < 5 || N > pow(10,9))
{
printf("\nNumber not in the valid range was inputted. \n"
"Please reenter the value: ");
scanf("%lf",&N);
}
else
{
floored = floor(N);
prime = twinPrime(floored);
printf("The largest twin prime pair not above %d is (%d,%d)",floored,prime - 2,prime);
printf("\nPlease re-enter the value:");
scanf("%lf",&N);
}
}
printf("\nProgram successfully terminated.");
return 0;
}
int twinPrime(int m)
{
int p = 3;
int q = 5;
for (; q < m - 1; q += 2)
{
if (IsPrime(q))
{
if (q - p == 2)
{
continue;
}
p = q;
}
}
return q;
}
int IsPrime(unsigned int number)
{
if (number <= 1) return 0; // zero and one are not prime
if ((number > 2) && ((number % 2) == 0)) return 0; //no even number is prime number (bar 2)
unsigned int i;
for (i=2; i*i<=number; i++)
{
if (number % i == 0) return 0;
}
return 1;
}Stack Overflow用户
发布于 2015-08-05 04:45:06
你正在研究素数“直到”一个给定的数字N。
在这类问题中，将信息存储在素数表和复合数字表中的效率更高(尽管在内存空间中更昂贵)，比如埃拉托斯提尼筛。
一旦你在表中填写了那些数字是素数和复合数的信息，那就只是在表上迭代来寻找孪生素数，不管它们在哪里。
但是，虽然您通知用户所有的都会显示出孪生素数，但实际上您的程序所做的只是试图只显示最新的。
请弄清楚你计划的目标是什么。
另一方面，您要在innest循环中重新定义标识符smallint，这无疑是一个逻辑错误。
如果不能使用数组来存储Eratosthenes的筛子，那么我将在这里向您展示一种不难实现的方法(当然，它并不是最有效的方法；不过，它将避免大量的冗余计算)。
孪生素数(大于4)可以有两种不同的形式：
- 6k-1，6k+1
- 6k+1，6k+5
因此，我将跳过具有形式6k+1，6k+5的数字序列，对于k= 0，1，2，3，.，所以我只分析序列中的奇数：
- 5、7、11、13、17、19、23、25、29、31、35、37、41、43、47、49、.
这可以通过添加2，4，2，4，2，4.
所以，我们可以拿第一对，比如说5和7。
我们用形式6k+1和6k+5的奇数除以它们中最大的平方根(sqrt(7))。
如果较少的数字(在本例中为5)可以被某个数字整除，我们在列表中选择以下数字，即11，然后除以到目前为止用来测试7是否为素数的所有数字。从这里开始，我们将7和11除以一起，再除以其余的数，直到sqrt(11)，以此类推。
注意，对于大数字，6k+1和6k+5有非常相似的平方根。
如果发生了相反的情况，即对于对(5，7)，这对夫妻的最大元素(在本例中为7)可以被其他数字整除，那么我们会丢弃这两个元素(5和7)，并选择列表中的以下两个元素(在本例中为11和13)。因此，我们从零开始搜索(即，除以小数字)。
最后，如果循环结束时没有为这对夫妇的任何元素找到除数(这确实是6和7的情况)，那么我们可以告知这对夫妇是孪生素数。
(或者我们可以保持沉默)。
然后，我们放弃最小元素(在本例中为5)，保留最大元素(在本例中为7)。
因为我们已经知道7是素数，所以我们只选择上面列表中的以下元素(在本例中是11)，并且只搜索它的除数。
我认为我所解释的方法将避免大量的冗余计算.
此外，有必要保持最新的一对孪生素数的发现。我想我没有必要向你们解释如何做到这一点。
https://stackoverflow.com/questions/31823245
复制相似问题
腾讯云开发者
