// ////////////////////////////////////////////////////////
// # Title
// Pseudo-Fortunate Numbers
//
// # URL
// https://projecteuler.net/problem=293
// http://euler.stephan-brumme.com/293/
//
// # Problem
// An even positive integer `N` will be called admissible, if it is a power of 2 or its distinct prime factors are consecutive primes.
// The first twelve admissible numbers are 2,4,6,8,12,16,18,24,30,32,36,48.
//
// If `N` is admissible, the smallest integer `M > 1` such that `N+M` is prime, will be called the pseudo-Fortunate number for `N`.
//
// For example, `N=630` is admissible since it is even and its distinct prime factors are the consecutive primes 2,3,5 and 7.
// The next prime number after 631 is 641; hence, the pseudo-Fortunate number for 630 is `M=11`.
// It can also be seen that the pseudo-Fortunate number for 16 is 3.
//
// Find the sum of all distinct pseudo-Fortunate numbers for admissible numbers `N` less than `10^9`.
//
// # Solved by
// Stephan Brumme
// July 2017
//
// # Algorithm
// The problem description starts with "an __even__ positive integer [...]" and continues with "[...] its distinct prime factors are consecutive primes.".
// Therefore any admissible number must be a multiple of 2 and its prime factors must start with 2, 3, 5, 7, ... without any gap.
// Its general form is: `2^a * 3^b * 5^c * ...` where a exponent is only zero if all following exponents are zero, too.
// The highest relevant base (prime) is 23 because `2^1 * 3^1 * 5^1 * 7^1 * 9^1 * 11^1 * 13^1 * 17^1 * 19^1 * 23^1 = 223092870 < 10^9`.
// Extending the series with `29^1` would exceed `10^9`.
//
// In step 1 of my algorithm I create all such admissible numbers up to `10^9` in ascending order:
// - put a 2 in the automatically sorted ''todo'' container, its highest prime factor is 2 (index 0 of ''factors'')
// - then repeat until ''todo'' is empty:
// - pick the lowest number from ''todo'' and store it in ''admissible''
// - multiply the same number by all values of ''factor[0 ... index+1]'' (those are the prime factors) and store them in ''todo'' (if `< 10^9`)
//
// In step 2 I run a simple prime sieve (trial division) to find all prime numbers up to `sqrt{10^9}`.
// Step 3 needs these prime numbers to run a primality test on each admissible number's right neighbors.
// Admissible numbers are always even, therefore only the numbers +3, +5, +7, +9, ... have to be checked.
//
// # Note
// There are a few optimization tricks:
// - some admissible numbers are smaller than the prime numbers generated in step 2 ==> simple linear search in ''primes''
// - for this specific range, not all primes in step 2 are actually needed ==> it's sufficient to have all primes up to `sqrt{2.8 * 10^8}` ==> 30% faster
#include
#include
#include