runtah: UVa 10948 The Primary Problem

Saturday, August 13, 2016

UVa 10948 The Primary Problem

#include <cstdio>
#include <iostream>
using namespace std;
bool ver[10000500];
int sieve()
{
 int i, j, k=0;

 //lst[k++]=2;
 for (i=3 ; i<=10000000 ; i+=2)
 {
 if (!ver[i])
 {
 //lst[k++]=i;
 for (j=3 ; i*j<=10000000 ; j+=2)
 {
 ver[i*j]=true;
 }
 }
 }
 //lst[0]=2;

 return k;
}

int main()
{
 sieve();
 int n, i;
 bool found;

 while (std::cin >> n && n)
 {
 std::cout << n << ":" << std::endl;

 if ((((n-2)&1) && !ver[n-2]) || (n-2 == 2))
 {
 std::cout << "2+" << n-2 << std::endl;
 continue;
 }
 found = false;
 for (i=3 ; i<=((n+1)/2) ; i+=2)
 {
 if (!ver[i] && !ver[n-i] && (n-i)&1)
 {
 std::cout << i << "+" << n-i << std::endl;
 found = true;
 break;
 }
 }
 if (!found) std::cout << "NO WAY!" << std::endl;
 }
 return 0;
}

Go to link download