Primes (Gym-102267B)

1837 ワード
# その他 OJ 数論——素性テスト

Problem Description


A prime number is a natural number greater than 1 and has exactly 2 divisors which are 1 and the number itself.
You are given a prime number nn, find any 2 prime numbers aa and bb such that a+b=n or state that no such pair of primes exists.

Input


The input contains a single prime number nn(2≤n≤107).

Output


If there doesn't exist any 2 primes such that their summation is equal to nn then print -1, otherwise print the 2 primes on a single line separated by a space.

Examples


input
5
output
2 3
input
11
output
-1
題意:素数nを与え、a+b=nとなるように素数対a、bを探し、素数対a、bがa、bを出力する場合、出力-1
考え方:素数をふるい取った後、前から後ろへの暴力をn/2に掃けばよい.素数iごとに、n-iが素数であるかどうかを判断する

Source Program

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
#define Pair pair
const int MOD = 1E9+7;
const int N = 10000000+5;
const int dx[] = {1,-1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;

int primes[N],cnt;
bool bPrime[N];
void getPrime(int n) {
    bPrime[0]=true;
    bPrime[1]=true;
    for(int i=2; i<=n; i++) {
        if(!bPrime[i])
            primes[cnt++]=i;
        for(int j=0; j

EC 2、CloudFront、pm 2、NGINX(2)を備えたSSR導入ポリシー
org.apache.hadoop.hdfs.server.namenode.NotReplicatedYetException