Algebra Homework, 2a

//Dimitar Atanasov 45382

//2143 5003 9293 1613 4493

//Date: 05.04.2020

#include <iostream>

using namespace std;

int main()
{
    const int n = 10000;
    bool isPrime[n + 1];
    memset(isPrime, true, sizeof(isPrime)); //set all values to true

    //I use a sieve for O(1) isPrime check
    for (int p = 2; p*p <= n; p++)
    {
        if (isPrime[p] == true)
        {
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }
    //Theorem: The number between every pair of prime twins is divisable by 6(because it is divisable by 2 and 3)
    //Thats why when we iterrate through twin primes we start with 6k and add 6 in every step
    //where k = 2, because 5 and 7 are illegal by definition of the problem
    int maxi = sqrt(n); // i*(i+2) < 10000
    int p1;
    int p2;
    int p; //result number
    for(int i = 6*2; i < maxi; i += 6)
    {
        p1 = i - 1;
        p2 = i + 1;
        if(isPrime[p1] && isPrime[p2]) //start searching for p, only if p1 & p2 are prime twins
            for(int j = 1; (p1 * p2 * j) - 2 < n; j++)
            {
                p = (p1 * p2 * j) - 2;
                if(isPrime[p] && p % 10 == 3)
                    cout << p << " ";
            }
    }
    return 0;
}