primes_up_to_billion.cpp File Reference

Compute prime numbers upto 1 billion. More...

#include <cstring>
#include <iostream>

Include dependency graph for primes_up_to_billion.cpp:

Functions
void	Sieve (int64_t n)
int	main ()

Variables
char	prime [100000000]

Detailed Description

Compute prime numbers upto 1 billion.

See also

prime_numbers.cpp sieve_of_eratosthenes.cpp

Function Documentation

main()

int main

(

void

)

Main function

           {
    Sieve(100000000);
    int64_t n;
    std::cin >> n;  // 10006187
    if (prime[n] == '1')
        std::cout << "YES\n";
    else
        std::cout << "NO\n";
 
    return 0;
}

Here is the call graph for this function:

Sieve()

void Sieve

(

int64_t

n

)

Perform Sieve algorithm

                      {
    memset(prime, '1', sizeof(prime));  // intitize '1' to every index
    prime[0] = '0';                     // 0 is not prime
    prime[1] = '0';                     // 1 is not prime
    for (int64_t p = 2; p * p <= n; p++) {
        if (prime[p] == '1') {
            for (int64_t i = p * p; i <= n; i += p)
                prime[i] = '0';  // set all multiples of p to false
        }
    }
}

Variable Documentation

prime

char prime[100000000]

array to store the primes