如何将一个数字表示为质数之和？

Question

让我们来寻找1到1000之间所有可以表示为两个质数之和的数字，例如8=3+5，24=13+11。

现在可以通过迭代1到1000之间的质数列表以O(n^2)的时间复杂度完成此操作。

是否有一种方法可以以小于O(n^2)的时间复杂度完成相同的操作？是否有一种线性时间的方法来做到这一点？

- user1822249

---

哥德巴赫猜想是数论和数学中最古老、最为著名的未解决问题之一。它的表述如下： 每个大于2的偶数都能够表示为两个质数的和。 - Mitch Wheat

如果只允许不同的质数呢？ - user1822249

Answer 1

对于我们现在所知道的所有偶数，它们都可以表示为两个质数的和（详见哥德巴赫猜想）。

对于所有奇数，如果它可以表示为两个质数的和，则其中一个必须是2，另一个应该是一个奇素数。

因此，总数应该是（1000/2-1）+（从3到997的素数计数），

其中，

（1000/2-1）是4、6、8、10……等数列的总数，

（从3到997的素数计数）是5（2+3）、7（2+5）、9（2+7）、13（2+11）等数列的总数。

- zTrix

Answer 2

创建一个由1000个布尔值组成的数组p。如果数字i是质数，则将p[i]设置为true，否则设置为false。

然后，该算法的时间复杂度为O(N^2)：在外层循环中遍历1到1000之间的数字k，然后在内层循环中遍历所有大于k的质数x，并检查是否存在一个质数使得p[k-x]为true。

for k in 1..1000
    for x in primes greater than k
        if (p[x-k])
            print k can be represented as x plus (x-k)
            break

我怀疑检查1000个数字的总运行时间为O(N)时，检查是否可以在恒定时间内完成，因为目前计算机辅助验证的速度相对较慢。

- Sergey Kalinichenko

Answer 3

import java.util.Scanner;

public class SumOfNPrmNos_2 {

    public static void main(String[] args) {
        int swap,sum=0;
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter Number Range From ");
        int small=sc.nextInt();
        System.out.println("Enter Number Range To ");
        int big=sc.nextInt();
        for (int i =small+1 ; i<big; i++) {
            char check='T';
            for (int j=2 ; j<=Math.sqrt(i) ; j++){
                if(i%j==0){
                    check='F';
                     break;
                }
            }
            if(check=='T'){
                sum=sum+i;
            }
        }
        System.out.println("Sum Is : = "+sum);

    }
}

- Saurabh Pawar

---

一些解释会很好。 - Geshode

Answer 4

1！1对于这个问题是一个好的公式。首先，进行1000 + 1除以5x + 38的计算。这是根据ATF定理得出的。尝试一下，你会得到答案。

- user7864921

Answer 5

解释：在这里，我创建了一个用于检查输入数字是否为质数的用户定义函数。该数字被分为两部分，第一部分是num-1，第二部分是1（它们的和等于num）。现在，第一个数字递减，第二个数字递增，直到它们变得相等或更大。对于每个这样的数字，我判断它们是否都是质数，如果都是质数，则使用break语句跳出循环并打印这些数字。

   #include<stdio.h>
    int prime(int);
    int main()
    {
            int num, r1, r2, i, j, c=0;
            printf("enter number\n");
            scanf("%d", &num);

            for(i=num-1, j=1; i>=j; i--, j++)   //this divides numb
            {
                    r1=prime(i);
                    r2=prime(j);

                    if(r1==1 && r2==1)
                    {

                            printf("Numbers are %d and %d\n", i, j);
                            c++;
                    }


            }
            if(c==0)
                    printf("cannot be expressed as sum of primes\n");
    }
    int prime(int n)
    {
            int i;
            for(i=2; i<=n; i++)
                    if(n%i==0)
                            break;
            if(n==i)
                    return 1;
            else
                    return 0;
    }

- arvind

---

这是我写的一小段C代码，欢迎提出任何建议。 - arvind