01. Primality Test

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
  vector<int> primes(n + 1, true);
  for(int i = 2; i <= n; i++)
    for (int j = i * 2; j <= n; j += i) primes[j] = false;
  return primes[n];
}

int main()
{
  int n;
  cout << "Enter a number: ";
  cin >> n;
  cout << n << " is prime is " << boolalpha << isPrime(n);
  return 0;
}

OUTPUT: 
    Enter a number: 10000
    10000 is prime is false

OUTPUT:
    Enter a number: 100001
    100001 is prime is false