4

让我们看看我们想要找到 1 到 1000 之间的所有数字，它们表示为两个素数之和。例如 8 = 3+5, 24 = 13+11

现在这可以通过遍历 1 到 1000 之间的素数列表在 O(n^2) 中完成。

有没有在小于 O(n^2) 的时间内做同样的事情。有没有一种方法可以在线性时间内做到这一点？

4

5 回答 5

8

对于我们现在知道的所有偶数，它们可以表示为 2 个素数之和（参见哥德巴赫猜想）

对于所有的奇数，如果可以表示为2个质数之和，其中一个一定是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) ...

于 2013-02-06T03:28:31.823 回答
2

制作一个包含 1000 个布尔值的数组p。设置p[i]为true如果i是素数，false否则。

然后O(N^2)算法变得简单：k在外循环中遍历数字 1 到 1000，然后遍历所有x大于k内循环的素数，并检查是否存在这样的素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

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

于 2013-02-06T03:41:22.423 回答
0

1！1 是一个很好的公式。首先，1000 + 1 除以 5x + 38。这是根据 ATF 定理。试试这个，你会得到答案。

于 2017-04-14T00:57:44.180 回答
0 
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);

    }
}
于 2018-10-22T06:02:12.410 回答
0

说明：这里我做了一个用户定义的函数来检查输入数字的素数。这个数字分为两部分，第一部分是 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;
    }
于 2019-08-03T07:16:51.563 回答