#include <iostream>
#include <cmath>
using namespace std;
// Method 1: Simple approach - check divisibility
bool isPrimeSimple(int num) {
if (num <= 1)
return false;
if (num == 2)
return true;
if (num % 2 == 0)
return false;
for (int i = 3; i <= num / 2; i += 2) {
if (num % i == 0)
return false;
}
return true;
}
// Method 2: Optimized approach - check up to sqrt(n)
bool isPrimeOptimized(int num) {
if (num <= 1)
return false;
if (num <= 3)
return true;
if (num % 2 == 0 || num % 3 == 0)
return false;
for (int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0)
return false;
}
return true;
}
// Method 3: Sieve of Eratosthenes (most efficient for range)
void sieveOfEratosthenes(int n) {
bool prime[n + 1];
// Initialize all numbers as prime
for (int i = 0; i <= n; i++)
prime[i] = true;
prime[0] = prime[1] = false;
for (int p = 2; p * p <= n; p++) {
if (prime[p]) {
// Mark all multiples of p as not prime
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
// Print all prime numbers
cout << "Prime numbers from 2 to " << n << ":\n";
int count = 0;
for (int i = 2; i <= n; i++) {
if (prime[i]) {
cout << i << " ";
count++;
if (count % 10 == 0) // Print 10 numbers per line
cout << endl;
}
}
cout << "\n\nTotal prime numbers: " << count << endl;
}
// Print primes using simple method
void printPrimesSimple(int n) {
cout << "Prime numbers from 2 to " << n << ":\n";
int count = 0;
for (int i = 2; i <= n; i++) {
if (isPrimeOptimized(i)) {
cout << i << " ";
count++;
if (count % 10 == 0)
cout << endl;
}
}
cout << "\n\nTotal prime numbers: " << count << endl;
}
int main() {
int n, choice;
cout << "========== PRIME NUMBERS GENERATOR ==========\n\n";
cout << "Enter the value of n: ";
cin >> n;
if (n < 2) {
cout << "\nNo prime numbers exist below 2.\n";
return 0;
}
cout << "\nChoose method:\n";
cout << "1. Simple Method (slower for large n)\n";
cout << "2. Sieve of Eratosthenes (faster for large n)\n";
cout << "Enter choice: ";
cin >> choice;
cout << "\n";
if (choice == 1) {
cout << "***** METHOD 1: SIMPLE APPROACH *****\n\n";
printPrimesSimple(n);
}
else if (choice == 2) {
cout << "***** METHOD 2: SIEVE OF ERATOSTHENES *****\n\n";
sieveOfEratosthenes(n);
}
else {
cout << "Invalid choice! Using default method.\n\n";
printPrimesSimple(n);
}
// Additional information
cout << "\n\n***** PRIME NUMBER FACTS *****\n";
cout << "- 2 is the only even prime number\n";
cout << "- All other prime numbers are odd\n";
cout << "- Prime numbers are divisible only by 1 and themselves\n";
// Show prime checking example
cout << "\n***** EXAMPLE: HOW TO CHECK IF A NUMBER IS PRIME *****\n";
int example = 29;
cout << "Checking if " << example << " is prime:\n";
cout << "Check divisibility from 2 to √" << example << " (≈5.4)\n";
cout << example << " ÷ 2 = remainder " << example % 2 << " (not divisible)\n";
cout << example << " ÷ 3 = remainder " << example % 3 << " (not divisible)\n";
cout << example << " ÷ 5 = remainder " << example % 5 << " (not divisible)\n";
cout << "No divisors found → " << example << " is PRIME!\n";
// Quick reference
cout << "\n***** QUICK REFERENCE *****\n";
cout << "First 10 primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n";
cout << "Primes less than 20: 2, 3, 5, 7, 11, 13, 17, 19\n";
cout << "Primes less than 50: 15 prime numbers\n";
cout << "Primes less than 100: 25 prime numbers\n";
return 0;
}
Comments
Post a Comment