Number Theory

#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

int prime[100000000];
int maxVal = 1e6;

int gcd(int x, int y)
{
    return y == 0 ? 1 : gcd(y, x  % y);
}

int lcm(int x, int y)
{
    return x * y / gcd(x, y);
}
void printPrime()
{
    vector<int> vec;
    for(int counter = 2; counter <= maxVal; counter++)
    {
        if(prime[counter])
            vec.push_back(counter);
    }
    int vSize = vec.size();
    cout << "The Primes are : " << vSize << endl;
    for(int counter = 0; counter < vSize; counter++)
        cout << vec[counter] << " ";
}

void naivePrimeMethod()
{
    memset(prime, true, sizeof prime);
    for(int counter = 2; counter <= maxVal; counter++)
    {
        for(int counter2 = 2; counter2 < counter; counter2++)
        {
            if(counter % counter2 == 0)
            {
                prime[counter] = false;
                break;
            }
        }
    }
    printPrime();
}

void sqrtPrimeMethod()
{
    memset(prime, true, sizeof prime);
    for(int counter = 2; counter <= maxVal; counter++)
    {
        for(int counter2 = 2; counter2 * counter2 <= counter; counter2++)
        {
            if(counter % counter2 == 0)
            {
                prime[counter] = false;
                break;
            }
        }
    }
    printPrime();
}

void SieveMethod()
{
    memset(prime, true, sizeof prime);
    for(int counter = 2; counter * counter <= maxVal; counter++)
    {
        if(!prime[counter]) continue;
        for(int counter2 = counter * counter; counter2 <= maxVal; counter2 += counter)
        {
                prime[counter2] = false;
        }
    }
    printPrime();
}

void comparePrimes()
{
    while(1)
    {
        cout << "Enter MaxVal: " << endl;
        cin >> maxVal;
        clock_t begin = clock();
        naivePrimeMethod();
        clock_t end = clock();
        double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
        cout << setprecision(8) << "The time of Naive method is " << elapsed_secs << endl;
        begin = clock();
        sqrtPrimeMethod();
        end = clock();
        elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
        cout << setprecision(8) << "The time of Sqrt method is " << elapsed_secs << endl;
        begin = clock();
        SieveMethod();
        end = clock();
        elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
        cout << setprecision(8) << "The time of Sieve method is " << elapsed_secs << endl;
    }
}

int power(int x, int y)
{
    if(y == 0) return 1;
    int sqrt = power(x, y / 2);
    int result = sqrt * sqrt;
    return y % 2 == 0 ? result : x * result;
}

int main(){
    comparePrimes();
    return 0;
}