How to find a number as a sum of prime numbers?
Let's see if we want to find all the numbers from 1 to 1000, which are represented as the sum of two primes. for example 8 = 3 + 5, 24 = 13 + 11
This can now be done in O (n ^ 2) by iterating through a list of primes from 1 to 1000.
Is there a way to do the same in less than O (n ^ 2). Is there a way to do this in linear time?
source to share
Make an array p
of 1000 booleans. Set p[i]
to true
if i
is simple, false
otherwise.
Then the algorithm O(N^2)
becomes easy: go k
through the numbers from 1 to 1000 in the outer loop, then go through all prime numbers x
greater than k
in the inner loop and check if there is such that 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
I doubt if the check can be done at a constant time for the full runtime O(N)
for 1000 numbers, as the auto check is currently happening at rather slow speeds .
source to share
For all even numbers that we know now, they can be represented as the sum of two primes (see Goldbach's conjecture )
For all odd numbers, if they can be represented as a sum of two primes, one of them must be 2 and the other must be an odd prime.
So the total should be (1000/2 - 1) + (number of primes from 3 to 997),
wherein,
(1000/2 - 1) - total number of series 4, 6, 8, 10 ...
(the number of primes from 3 to 997) represents the total number of rows 5 (2 + 3), 7 (2 + 5), 9 (2 + 7), 13 (2 + 11) ...
source to share
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);
}
}
source to share
Explanation: Here I made a custom function to check the prime of the entered number. This number is divided into two parts: the first is num-1, and the second is 1 (their sum is num), now the first decreases, and the second increases until they become equal or greater, for each of these numbers i find if both are simple, if both are simple then break is used to break out of the loop and print these numbers.
#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;
}
source to share