Golbach’s Conjecture: Any even number can be expressed as a summation of two prime numbers.
This idea is used to solve the problem.
- if the number is odd then .ie 49 thn 2,3 and goldbach conjechture of (49-5)
- can be expressed as sum of 2 primes.
- if the number is even then 2,2 and goldbach conjechture of (number-4)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <iostream> #include <cstdio> #include <cmath> using namespace std; int arr[10000001]; int prime[5000002][2]; int goldbach_Conjecture(int n) { int x = n/2; if(prime[x][0]!=0 && prime[x][1]!=0) return prime[x][0]; for(int i=n-2;i>=2;i--) { if(arr[i]==0 && n-i>=2 && arr[n-i]==0) { prime[x][0]=i; prime[x][0]=n-i; return i; } } } int main() { int N; int a,b; int k=1; arr[0]=1; arr[1]=1; for(int i=2;i<sqrt(10000001);i++) { if(arr[i]==0) { for(int j=i+i;j<10000001;j+=i) { arr[j]=1; } } } while(scanf("%d",&N)!=EOF) { if(N<8) cout<<"Impossible.\n"; else { if(N%2) { cout<<2<<" "<<3<<" "; a = goldbach_Conjecture(N-5); cout<<a<<" "<<N-5-a<<"\n"; } else { cout<<2<<" "<<2<<" "; b = goldbach_Conjecture(N-4); cout<<b<<" "<<N-b-4<<"\n"; } } } return 0; } |