OJ Board

Code: Select all

#include <cstdio>
#include <iostream>
#include <cmath>
#define MAX 10000100
#define PMAX 664600
#define int64 long long
using namespace std;

bool base[MAX+2];
int64 prime[PMAX+2];
void getPrime()
{
	int i2,cnt=0;
	int sq=sqrt(MAX);
	for(int i=3;i<=sq;i+=2)
	{
		if(!base[i])
		{
			i2=i*2;
			for(int j=i*i;j<=MAX;j+=i2)
				base[j]=true;
		}
	}
	prime[cnt++]=2;
	for(int i=3;i<=MAX;i+=2)
		if(!base[i]) {prime[cnt++]=i;}
}

int main()
{
	getPrime();
	int64 n,half,val;
	while(scanf("%lld",&n)==1)
	{
		bool flag=false;
		if(n<8 && n>=-7) cout<<"Impossible.\n";
		else{
			if(n<0){ flag=true;n=-n;}
			n=n-4;
			if(flag==true)
				cout<<"-2 -2 ";
			else
			cout<<"2 2 ";
			half=n/2;
			for(int i=0;prime[i]<=half;i++)
			{
				
				val = n-prime[i];
				if((val%2!=0 && !base[val]) || val==2)
				{
					if(flag)
						printf("-%lld -%lld\n",prime[i],val);
					else
					cout<<prime[i]<<" "<<val<<endl;
					break;
				}
			}
			
		}
	}
	return 0;
}

Code: Select all

Removed after AC . Codes were fine.There was an online judge problem . Now it's solved and all the solutions are accepted

Code: Select all

AC

Code: Select all

#include <iostream>
#include <vector>

#define MAX_N 10000000

using namespace std;

vector<int> primes;

void init() {
  vector<bool> removed(MAX_N + 1);
  primes.reserve(665000); //There are 664579 prime numbers within 10000000
  primes.push_back(2);
  int i = 3;
  for (; i <= MAX_N; i += 2) {
    if (!removed[i]) {
      primes.push_back(i);
      int s = i + i;
      for (; s <= MAX_N; s += i) {
        removed[s] = true;
      }
    }
  }
}

//The index of a prime p in primes array that is the biggest prime not bigger than n.
int index_of_prime(int n) {
  int r = -1;
  int i = 0;
  int j = primes.size();
  while (i != j) {
    int mid = (i + j) / 2;
    if (primes[mid] == n) {
      r = mid;
      break;
    }
    else if (primes[mid] > n) {
      j = mid;
      if (i == j) {
        r = mid - 1;
      }
    }
    else {
      i = mid + 1;
      if (i == j) {
        r = mid;
      }
    }
  }
  return r;
}

inline bool is_prime(int n) {
  return n < 2 ? false : primes[index_of_prime(n)] == n;
}

bool backtrack(int n, int q, vector<int> & a) {
  int r = false;
  if (q == 1) {
    if (is_prime(n)) {
      a.push_back(n);
      r = true;
    }
  }
  else {
    int i = index_of_prime(n);
    q--;
    for (; i >= 0; i--) {
      if (backtrack(n - primes[i], q, a)) {
        a.push_back(primes[i]);
        r = true;
        break;
      }
    }
  }
  return r;
}

inline bool four_primes(int n, vector<int> & a) {
  if (n < 8)
    return false;
  return backtrack(n, 4, a);
}

int main() {
  init();
  int n;
  while (cin >> n) {
    vector<int> a;
    if (four_primes(n, a)) {
      for (int i = 0; i < 4; i++) {
        if (i)
          cout << ' ';
        cout << a[i];
      }
      cout << endl;
    }
    else {
      cout << "Impossible." << endl;
    }
  }
  return 0;
}

Code: Select all

#!/usr/bin/env ruby

require_relative 'test_helper'

PRIMES = []

def produce_primes(n)
  removed = Array.new(n + 1, false)
  PRIMES << 2
  i = 3
  while i <= n
    if !removed[i]
      PRIMES << i
      s = i + i
      while s <= n
        removed[s] = true
        s += i
      end
    end
    i += 2
  end
end

def is_prime(n)
  yes = false
  i = 0
  j = PRIMES.size
  while i != j
    mid = (i + j) / 2
    if PRIMES[mid] == n
      yes = true
      break
    elsif PRIMES[mid] > n
      j = mid
    else
      i = mid + 1
    end
  end
  yes
end

s = 8
e = 10000000
produce_primes(e)

test_file = File.expand_path(__FILE__)
test(test_file) do |input, output|
  input = File.open(input, 'wb')
  (s..e).each do |i|
    input.puts i
  end
  input.close
end

count = 0
i = s
w = []
check_result(test_file) do |result|
  result = File.open(result, 'rb')
  result.each_line do |line|
    a = line.split.map! {|e| e.to_i}
    if a.reduce(:+) == i && a.all? {|e| is_prime(e)}
      count += 1
    else
      w << (i - s + 1) #record the wrong line number
    end
    i += 1
  end
  result.close
end

if count == e - s + 1
  puts 'OK'
else
  puts 'The following line(s) of the result file are wrong:'
  puts w.join(', ')
end

Code: Select all

#include<stdio.h>
int isPrime(long num)
{
    long i;
    for(i=2;i<=num/i;i++)
        if(num%i==0)
            return 0;
    return 1;
}
int main()
{
   
    long i,k=1,j,prime[78600],n,a,b,c,d,op,from,to,m,l,p;
    for(i=2;i<=1000000;i++)
       if(isPrime(i)==1)
            prime[k++]=i;
    while(scanf("%ld",&n)&&n!=0)
    {
        if(n<8)
        {
            printf("Impossible.\n");
            continue;
        }
        a=b=c=d=0;
         for(i=1;i<k;i++)
         {
             if(prime[i]>=n)
                break;
              for(j=i;j<k;j++)
             {
                 if(prime[j]>=n)
                    break;
                 for(l=j;l<k;l++)
                 {
                     if(prime[l]>=n)
                        break;
                    op=n-prime[i]-prime[j]-prime[l];
                    from=l;
                    to=k;
                    while(from<to)
                    {
                        m=(from+to)/2;
                        if(op>prime[m])
                            from=m+1;
                        else if(op==prime[m])
                        {
                            from=m;
                            break;
                        }
                        else if(op<prime[m])
                            to=m;

                    }
                    if(prime[from]==op)
                    {
                        a=prime[i];
                        b=prime[j];
                        c=prime[l];
                        d=prime[from];
                        break;
                    }
                }
                if(a+b+c+d==n)
                    break;
             }
             if(a+b+c+d==n)
                break;
        }
        if(a+b+c+d==0)
            printf("%ld %ld %ld %ld\n",a,b,c,d);
        else
            printf("Impossible.\n");



    }
    return 0;
}