121 lines
2.3 KiB
C++
121 lines
2.3 KiB
C++
#include <vector>
|
||
#include <unordered_set>
|
||
#include <iostream>
|
||
#include <cmath>
|
||
#include <algorithm>
|
||
#include <chrono>
|
||
|
||
/*
|
||
Given an even number ( greater than 2 ), return two prime numbers whose
|
||
sum will be equal to given number.
|
||
|
||
NOTE A solution will always exist. read Goldbach’s conjecture
|
||
|
||
Example:
|
||
|
||
|
||
Input : 4
|
||
Output: 2 + 2 = 4
|
||
|
||
If there are more than one solutions possible, return the lexicographically
|
||
smaller solution.
|
||
*/
|
||
|
||
/*
|
||
* My understanding is:
|
||
* The first solution time complexity is O(n^2/log_n) + O(n) memory complexity.
|
||
* The second solution id O(n^2) complexity + O(0) memory complexity.
|
||
*/
|
||
#define SOLUTION 1
|
||
|
||
#if SOLUTION == 1
|
||
|
||
std::vector<size_t> primes;
|
||
std::unordered_set<size_t> primes_set;
|
||
|
||
void init_primes(const size_t n)
|
||
{
|
||
|
||
std::vector<bool> prime_table(n/2+1, true); // Only odd numbers.
|
||
primes.push_back(2);
|
||
|
||
for (auto p = 3; p <= n; p+=2) {
|
||
if ( prime_table[p/2] ) {
|
||
primes.push_back(p);
|
||
for ( int j = p*3; j <= n; j+=p*2 ) {
|
||
prime_table[j/2] = false;
|
||
}
|
||
}
|
||
}
|
||
|
||
primes_set.insert(primes.begin(), primes.end());
|
||
}
|
||
|
||
std::vector<int> primesum(int A)
|
||
{
|
||
for ( int p : primes ){
|
||
if ( primes_set.find(A-p) != primes_set.end() ) {
|
||
return {p, A-p};
|
||
}
|
||
}
|
||
|
||
return {};
|
||
}
|
||
|
||
#elif SOLUTION == 2
|
||
|
||
bool is_prime(int a)
|
||
{
|
||
if ( a <2 )
|
||
return false;
|
||
|
||
int end = std::floor(std::sqrt(a));
|
||
for ( int i = 2; i <= end; ++i ){
|
||
if ( a % i == 0) {
|
||
return false;
|
||
}
|
||
}
|
||
return true;
|
||
}
|
||
|
||
std::vector<int> primesum(int A)
|
||
{
|
||
|
||
for ( int i = 2; i < A; ++i) {
|
||
if ( is_prime(i) && is_prime(A-i) ){
|
||
return {i,A-i};
|
||
}
|
||
}
|
||
return {};
|
||
}
|
||
|
||
#endif
|
||
|
||
void solve_and_print(int A){
|
||
auto r = primesum(A);
|
||
std::cout << r[0] << ' ' << r[1] << std::endl;
|
||
}
|
||
|
||
int main()
|
||
{
|
||
auto begin = std::chrono::high_resolution_clock::now();
|
||
|
||
#if SOLUTION == 1
|
||
init_primes(16777218);
|
||
#endif
|
||
|
||
solve_and_print(4);
|
||
solve_and_print(10);
|
||
|
||
solve_and_print(16777214);
|
||
solve_and_print(16777218);
|
||
|
||
for ( int i = 4; i < 1000000; i+=2 ){
|
||
primesum(i);
|
||
}
|
||
|
||
auto end = std::chrono::high_resolution_clock::now();
|
||
std::chrono::duration<double> seconds = end - begin;
|
||
std::cout << "Time: " << seconds.count() << std::endl;
|
||
}
|