Moderator: Board moderators
Code: Select all
AC!! THX VERY MUCH!
THX FOR THE CORRECT I/O!After knowing that I had this misconception (not knowing that the diff must be +ve =.=)mmonish wrote:Try this case
input
10
output
10 is the sum of 3 and 7.
the difference between the two primes must be positive.
Code: Select all
#include <iostream>
#define HM 100000000
using namespace std;
bool prime_mark [HM];
//sieve the primes with the "Eratosthenes Prime Sieve"
//until 100'000'000 and not until the square root.
void prime_sieve (int n) {
int s = n;
int num_primes = 1;
for (int i=2; i < n; i+=2 ) {
prime_mark[i] = false;
prime_mark[i+1] = true;
}
prime_mark[0] = prime_mark[1] = false;
prime_mark[2] = true;
for( int i=3; i<s; i+=2 ){
if (prime_mark[i]) {
num_primes++;
for (int j=3*i; j < n; j+=(2*i)){
prime_mark[j] = false;
}
}
}
}
bool isEven (int n){
if (n%2 == 0){
return true;
}
else {
return false;
}
}
int main() {
prime_sieve (HM);
int n;
int p1 = -1;
int p2 = -1;
while (!cin.eof()){
cin >> n;
// if input number is odd: there is only the possibility to form an odd number with an even + an odd number.
// The only even prime is 2. so for this case, test if n-2 is a prime.
if (!(isEven(n))){
if (prime_mark[n-2]){
cout << n << " is the sum of 2 and " << n-2 << "." << endl;
}
else {
cout << n << " is not the sum of two primes!" << endl;
}
}
// if input number is even: it must be a sum of two odd numbers, since there are no two distinct even primes
/*
1. divide n by 2, save to half
2. if half is even, set p1 to half-1 and p2 to half+1;
else (if half is odd) set p1 to half-2 and p2 to half+2.
3. check if p1 and p2 are primes (if yes, you have found a minimized sum for your n and you can break)
4. else p1 -= 2 and p2 +=2 and check again if both are primes and so forth...
*/
else{
//1. divide n by 2, save to half
int halfn = n/2;
//2. if half is even, set p1 to half-1 and p2 to half+1;
if ((isEven(halfn))) {
p1 = halfn-1;
p2 = halfn + 1;
if ( prime_mark[p1] && prime_mark[p2]){
}
}
// else (if half is odd) set p1 to half-2 and p2 to half+2.
else {
p1 = halfn - 2;
p2 = halfn + 2;
}
//3. check if p1 and p2 are primes (if yes, you have found a minimized sum for your n and you can break)
//4. else p1 -= 2 and p2 +=2 and check again if both are primes and so forth...
while (!prime_mark[p1] || !prime_mark[p2]){
if ( prime_mark[p1] && prime_mark[p2]){
break;
}
else{
p1 = p1 -2;
p2 = p2 + 2;
}
}
// Make sure you are not going minus
// When you did not have this check, you were getting:
/*
6 is the sum of -7 and 13.
4 is the sum of -7 and 11.
2 is the sum of -9 and 11.
*/
if ( p1>0 && p2>0) {
cout << n << " is the sum of " << p1 << " and " << p2 << "." << endl;
}
else {
cout << n << " is not the sum of two primes!" << endl;
}
}
}
return 0;
}
,