blocks|key|4889971|text|创建一个包含1000个布尔值的数组p。如果i是质数，则将p[i]设置为true，否则设置为false。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|4889972|然后，O(N%5E2)算法就变得简单了:在外部循环中遍历数字k+1到1,000，然后在内部循环中遍历所有大于k的素数x，并检查是否存在一个素数使得p[k-x]为true|4889973|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|code-block|syntax|javascript|4889974|我怀疑对于1000个数字because+computer-aided+verification+currently+proceeds+at+a+rather+slow+speeds的O(N)的总运行时间，可以在恒定的时间内执行检查。|4889975|entityMap|0|LINK|mutability|MUTABLE|url|https://www.egi.eu/case-studies/Goldbachs_conjecture.html^0|H|1|L|1|S|4|Z|4|19|5|0|3|6|S|1|1G|1|1K|1|1Z|6|26|4|0|0|2J|4|C|26|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@$9|X|A|Y|B|C]|$9|Z|A|10|B|C]|$9|11|A|12|B|C]|$9|13|A|14|B|C]|$9|15|A|16|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|17|8|@$9|18|A|19|B|C]|$9|1A|A|1B|B|C]|$9|1C|A|1D|B|C]|$9|1E|A|1F|B|C]|$9|1G|A|1H|B|C]|$9|1I|A|1J|B|C]]|D|@]|E|$]]|$1|H|3|I|5|J|7|1K|8|@]|D|@]|E|$K|L]]|$1|M|3|N|5|6|7|1L|8|@$9|1M|A|1N|B|C]]|D|@$9|1O|A|1P|1|1Q]]|E|$]]|$1|O|3|-4|5|6|7|1R|8|@]|D|@]|E|$]]]|P|$Q|$5|R|S|T|E|$U|V]]]]

Make an array <code>p</code> of 1000 booleans. Set <code>p[i]</code> to <code>true</code> if <code>i</code> is prime, and <code>false</code> otherwise.

Then the <code>O(N^2)</code> algorithm becomes easy: go through numbers <code>k</code> 1 through 1000 in the outer loop, then go through all primes <code>x</code> greater than <code>k</code> in an inner loop, and check if there exists a prime such that <code>p[k-x]</code> is <code>true</code>:

<pre><code>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
</code></pre>

I doubt that the check could be performed in constant time for a total running time of <code>O(N)</code> for the 1000 numbers, <a href="https://www.egi.eu/case-studies/Goldbachs_conjecture.html" rel="nofollow">because computer-aided verification currently proceeds at a rather slow speeds</a>.

blocks|key|1539717|text|对于我们现在知道的所有偶数，它们可以表示为2个质数的和(参见Goldbach's+conjecture)。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1539718|对于所有的奇数，如果它可以表示为2个素数的和，那么其中一个一定是2，另一个应该是奇素数。|1539719|所以总数应该是(1000/2+-+1)+%2B(素数计数从3到997)，|1539720|其中，|1539721|(1000/2+-+1)是系列4、6、8、10的总数...|1539722|(质数从3到997)是系列5(2%2B3)、7(2%2B5)、9(2%2B7)、13(2%2B11)的总数...|1539723|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Goldbach%2527s_conjecture^0|U|L|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|V|8|@]|9|@$A|W|B|X|1|Y]]|C|$]]|$1|D|3|E|5|6|7|Z|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|10|8|@]|9|@]|C|$]]|$1|H|3|I|5|6|7|11|8|@]|9|@]|C|$]]|$1|J|3|K|5|6|7|12|8|@]|9|@]|C|$]]|$1|L|3|M|5|6|7|13|8|@]|9|@]|C|$]]|$1|N|3|-4|5|6|7|14|8|@]|9|@]|C|$]]]|O|$P|$5|Q|R|S|C|$T|U]]]]

For all the even numbers we know now, they can be represented as the sum of 2 prime numbers(see <a href="http://en.wikipedia.org/wiki/Goldbach%27s_conjecture" rel="noreferrer">Goldbach's conjecture</a>)

For all the odd numbers, if it can be represented as the sum of 2 prime numbers, one of the them must be 2, and the other should be an odd prime.

So the total number should be (1000/2 - 1) + (prime number count from 3 to 997),

in which, 

(1000/2 - 1) is the total number of series 4, 6, 8, 10...

(prime number count from 3 to 997) is the total number of series 5(2+3), 7(2+5), 9(2+7), 13(2+11) ...

blocks|key|1539771|text|1！1是一个很好的公式。第一个是1000+%2B1除以5x+%2B+38。这是根据ATF定理。试试这个，你就会得到答案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1539772|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

1 ! 1 is a good formula for this. first do, 1000 + 1 divided by 5x + 38. this is according to the ATF Theorem. try this and you will get the answer.

blocks|key|1539774|text|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%2B1+;+i<big;+i%2B%2B)+{
++++++++++++char+check='T';
++++++++++++for+(int+j=2+;+j<=Math.sqrt(i)+;+j%2B%2B){
++++++++++++++++if(i%25j==0){
++++++++++++++++++++check='F';
+++++++++++++++++++++break;
++++++++++++++++}
++++++++++++}
++++++++++++if(check=='T'){
++++++++++++++++sum=sum%2Bi;
++++++++++++}
++++++++}
++++++++System.out.println("Sum+Is+:+=+"%2Bsum);

++++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1539775|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>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&lt;big; i++) {
 char check='T';
 for (int j=2 ; j&lt;=Math.sqrt(i) ; j++){
 if(i%j==0){
 check='F';
 break;
 }
 }
 if(check=='T'){
 sum=sum+i;
 }
 }
 System.out.println("Sum Is : = "+sum);

 }
}
</code></pre>

blocks|key|5373304|text|说明:这里我做了一个用户定义的函数，用来检查输入数字的质数。这个数字分为两部分，第一部分是num-1，第二部分是1(它们的和等于num)，现在第一部分是递减的，第二部分是递增的，直到它们都相等或更大，对于这两个数字，我发现如果它们都是质数，如果它们都是质数，那么就使用break从循环中出来打印这些数字。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5373305|+++#include<stdio.h>
++++int+prime(int);
++++int+main()
++++{
++++++++++++int+num,+r1,+r2,+i,+j,+c=0;
++++++++++++printf("enter+number\n");
++++++++++++scanf("%25d",+&num);

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

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

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


++++++++++++}
++++++++++++if(c==0)
++++++++++++++++++++printf("cannot+be+expressed+as+sum+of+primes\n");
++++}
++++int+prime(int+n)
++++{
++++++++++++int+i;
++++++++++++for(i=2;+i<=n;+i%2B%2B)
++++++++++++++++++++if(n%25i==0)
++++++++++++++++++++++++++++break;
++++++++++++if(n==i)
++++++++++++++++++++return+1;
++++++++++++else
++++++++++++++++++++return+0;
++++}|code-block|syntax|javascript|5373306|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Explanation: here I made a user-defined function for checking prime of the input number. This number is divided into two parts first is num-1 and second is 1(their sum is equal to num), now the first one is decremented and second is incremented until they both become equal or greater, for each of these numbers, I find if both of them are prime, if both are prime , then break is used to come out of the loop and print those numbers.

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

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

 if(r1==1 &amp;&amp; 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&lt;=n; i++)
 if(n%i==0)
 break;
 if(n==i)
 return 1;
 else
 return 0;
 }
</code></pre>

Lets see we want to find all numbers between 1 to 1000 which are represented as a sum of two prime numbers. e.g 8 = 3+5, 24 = 13+11

Now this can be done in O(n^2) by iterating through the list of prime numbers between 1 to 1000.

Is there anyway of doing the same thing in less than O(n^2).Is there a method for doing this in linear time ?

How to find a number as a sum of prime numbers?

5位重磅专家聚焦 AI 时代开发者核心成长需求，带你深入解锁全栈进化、人机协作关键路径！点击报名到场：<a href="https://cloud.tencent.com/developer/salon/salon-2403/signup" target="_blank">https://cloud.tencent.com/developer/salon/salon-2403/signup</a> 
 <img src="https://qcloudimg.tencent-cloud.cn/raw/487c82639d2338df3ef66dfb1450601a.png"/>

腾讯技术创作特训营「年度论坛」正在报名中！

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

让我们看看，我们想要找到1到1000之间的所有数字，它们被表示为两个质数的和。例如8= 3+5，24 = 13+11现在，这可以在O(n^2)中通过迭代1到1000之间的质数列表来完成。有没有办法在O(n^2).Is以内做同样的事情?有没有一种方法可以在线性时间内做到这一点？

问如何找到一个质数和的数字？
EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何找到一个质数和的数字？EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何找到一个质数和的数字？
EN