Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
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

26  {
27  Sieve(100000000);
28  int64_t n;
29  std::cin >> n; // 10006187
30  if (prime[n] == '1')
31  std::cout << "YES\n";
32  else
33  std::cout << "NO\n";
34 
35  return 0;
36 }
Here is the call graph for this function:

◆ Sieve()

void Sieve ( int64_t  n)

Perform Sieve algorithm

13  {
14  memset(prime, '1', sizeof(prime)); // intitize '1' to every index
15  prime[0] = '0'; // 0 is not prime
16  prime[1] = '0'; // 1 is not prime
17  for (int64_t p = 2; p * p <= n; p++) {
18  if (prime[p] == '1') {
19  for (int64_t i = p * p; i <= n; i += p)
20  prime[i] = '0'; // set all multiples of p to false
21  }
22  }
23 }

Variable Documentation

◆ prime

char prime[100000000]

array to store the primes

std::cout
Sieve
void Sieve(int64_t n)
Definition: primes_up_to_billion.cpp:13
std::cin
std::memset
T memset(T... args)
prime
char prime[100000000]
Definition: primes_up_to_billion.cpp:10