如何找到既属于孪生素数又属于表亲素数的素数？

Question

我必须找出从 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)

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;
}

我使用了 unsigned 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;
}

这个主要函数给出孪生素数和表亲素数。但我想找到这两者的共同数字。这让我有点困惑。不知道怎么找公共号。

Answer 1

一个简单的解决方案（需要额外的内存 - 可能会被优化）是构建双胞胎和堂兄弟的列表并将这两个列表相交。

示例：

#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

Answer 2

通过一些簿记，您可以只计算一次每个素数。

这是 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}");
}

如何找到既属于孪生素数又属于表亲素数的素数？

How to find prime numbers that are member of twin prime as well as member of cousin prime?

c

primes