查找孪生素数-逻辑已完成，但在程序运行时不会打印任何内容

Question

孪生素数是一个质数，它恰好比比它小的最大素数大两个。例如，7是孪生素数，因为它正好是大于5的2。但17不是孪生素数，因为小于17的最大素数是13。

我对这个程序的逻辑如下：

*ask number of twin primes that want to be found
 *loop until desired number of twin primes are found
   *loop numbers 2 - 1million (declared as variable j)
    *check if that number 'j' is prime - if so flag it
     *if 'j' is not flagged, subtract 2 from 'j' (call that new number 'TPcheck')
      *Check if 'TPcheck' is a prime, if so, print 'TPcheck' and the first number 'j'

当我运行这个程序时，我输入了要找到的孪生质数的数量，但它只是继续运行，并且不会在屏幕上打印任何内容。我认为问题可能与循环和if语句的顺序有关(或者可能与它们的嵌套方式有关)，但我尝试了大量不同的方法，但都没有奏效。

下面是我的代码：

#include <stdio.h>
#include <stdlib.h>

int main()
{

int i = 2, count = 0, TPcheck, j, k, flag;
int numberofTwinPrimes;
printf("Enter how many twin primes you want to find");
scanf("%d", &numberofTwinPrimes);


while(count < numberofTwinPrimes)
{
    for(j = 2; j <= 1000000; ++j)
    {   for(i = 2; i < j; ++i)
        {
            if(j%i == 0)
            {
                flag = 1;                   
                continue;
            }

            if(flag == 0)
            {
                TPcheck = j - 2;
                for(k = 2; k < TPcheck; ++k)
                {
                    if(TPcheck%k == 0)
                    {
                        flag = 1;
                        continue;
                    }

                    if(flag == 0)
                    {
                        printf("%d\t %d\t", TPcheck, j);
                        count++;                
                    }
                }
            }           
        }

    }
}                       


return 0;

}

Answer 1

这个isPrime()函数比Fumu的建议更快：

/* function isPrime returns True if argument is prime number. */
boolean isPrime(int aNumber)
{
    int i;
    int limit;

    /* Numbers < 2 */
    if(aNumber < 2) { return False; }

    /* Even numbers. */
    if (aNumber % 2 == 0) { return aNumber == 2; }

    /* Odd numbers. */

    /* Only need to check odd divisors as far as the square root. */
    limit = (int)(sqrt(aNumber));
    for (i = 3; i <= limit; i += 2)
    {
        if( aNumber % i == 0) { return False; } 
    }

    /* Only prime numbers make it this far. */
    return True;
}

2是唯一的偶数，所以所有偶数都可以非常快地处理。奇数只需要使用小于或等于该数的平方根的奇数因子进行测试:9=3*3

有更快的方法，但它们需要构造质数表。对于您的程序来说，这样的东西似乎就足够了。

Answer 2

您用于检查数字是否质数的代码不正确。

你应该检查数字永远不能除以任何小于该数字的数字。

检查数字是否为质数的函数代码如下：

/* function isPrime returns True if argument is prime number. */
boolean isPrime(int aNumber)
{
    int i;

    if(aNumber < 2) { return False; } 
    else if (aNumber==2) {return True;}

    for i=2 to aNumber-1
    {
        if((aNumber%i) == 0){
          return False;
        } 
    }

    return True;
} 

我希望这能给你一些有用的想法。