Large Prime Check Using The Sieve Of Eratosthenes in C++

Filed Under: C++
Large Prime Check Using The Sieve Of Eratosthenes

In this article, we will learn the large prime check using the Sieve of Eratosthenes. For competitive programming, you must be very clear with the concept of Sieve of Eratosthenes. Even if you’re not a competitive programmer, it’s good to have a tight grip on this algorithm. It is very handy to work with prime numbers and related problems. First, we will go through the problem statement and then move toward the algorithm.

Also read: Prime Factorization Using The Sieve Of Eratosthenes in C++

Problem Statement

Given a number as input, check if this number is a prime number or not.

Note: The number can take large values, i.e. 1 <= N <= 1014

For example,

Number: 10
Output: Not a prime number

Number: 97
Output: Prime number

Number: 2147483647
Output: Prime number

Number: 8449771677
Output: Not a prime number

Number: 1324925285823
Output: Not a prime number

Number: 24874529710111
Output: Prime number

Number: 3593569369386677
Output: Not a prime number

Number: 12134345676707
Output: Prime number

Number: 100000000000
Output: Not a prime number

Concept of Large Prime Checks

The problem is really simple to figure out. We know that the maximum size of a sieve that is allowed is 107. We will take advantage of the fact that the factors of a number lie in the range 1 to square_root(num). This method would allow us to check for primes up to 1014. Below are the steps to code the algorithm.

  • Initialize a bitset of the size n = 107.
  • Initialize a vector primes to store prime numbers.
  • First, generate the prime sieve up to 107.
  • Once the sieve is ready, we will continue with the steps below.
  • Create a function bool is_prime(int num)
  • Inside this function, we will have two cases
    1. The number lie in the range: 0 <= num <= 107
      • return b[num] == 1
    2. Otherwise, we will have to check for the divisors of the number.
      • To do this, iterate over all the primes in the range 2 to square_root(num)
      • for(int i = 0; primes[i] * primes[i] <= num; i++)
        • if(num % primes[i] == 0)
          • return false
      • Otherwise, return true

Large Prime Check Using Sieve Of Eratosthenes C++ Program

#include <iostream>
#include <vector>
#include <bitset>

using namespace std;

const int n = 10000000;

// this operation takes O(1) time to initialize
// the bitset
bitset <10000000> b;
vector <int> primes;

void sieve()
{
	// set all bits
	b.set();

	b[0] = b[1] = 0;

	for(long long int i = 2; i <= n; i++)
	{
		if(b[i])
		{
			primes.push_back(i);

			for(long long int j = i * i; j <= n; j += i)
			{
				b[j] = 0;
			}
		}
	}
}

bool is_prime(long long int num)
{
	// here we will have two cases
	// 1. the number is in the range
	// 0 <= num <= n
	if(num <= n)
		return b[num] == 1;

	// 2. num >= n
	// we will find the divisors of this number
	// using a loop, this loop will
	// run in the range 2 to square_root(num)
	// if we find any divisor of this number
	// we will mark this number as non - prime
	for(long long int i = 0; primes[i] * (long long)primes[i] <= num; i++)
		if(num % primes[i] == 0)
			return false;

	// return true if it is not divisible by any of the numbers
	return true;
}

int main()
{
	// precompute the sieve
	sieve();

	cout << "Enter a number" << endl;
	long long int num;
	cin >> num;

	if(is_prime(num))
		cout << "Prime Number" << endl;
	else
		cout << "Not a prime number" << endl;

	return 0;
}
Large Prime Check Program
Large Prime Check Program

Output

Large Prime Check Output
Large Prime Check Output

Conclusion

Today, we learned to check if a large number is prime or not. To program the solution, we used the Sieve of Eratosthenes. The time complexity of this algorithm will be O(Nlog2(log2N) + O(N1/2)), here O(Nlog2(log2N)) is for generating the sieve and O(N1/2) for calculating the divisors. In the end, we coded a C++ program to check the validity of the algorithm. That’s all for today, thanks for reading.

Further Readings

To learn more about data structures and algorithms, please visit the following articles,

https://www.journaldev.com/60732/remove-consecutive-duplicates-from-string-cpp

https://www.journaldev.com/61078/reverse-a-stack-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content