9

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

 3 years ago
source link: https://www.journaldev.com/61242/large-prime-check-sieve-of-eratosthenes-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

Filed Under: C++

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 ProgramLarge Prime Check Program

Output

Large Prime Check OutputLarge 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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK