14. Maths and Problems

Prime Numbers

---

Definition

• A prime number is a whole number greater than 1 that has only two divisors - 1 and itself
• For example, 2, 3, 5, 7, 11, 13 are prime numbers
• Composite numbers have more than two divisors (4, 6, 8, 9, 10 etc.)

Checking if a Number is Prime

---

Naive Method

#include<iostream>
using namespace std;
 
// Basic method 
// Time Complexity: O(n) 
 
bool isPrime(int n) {
  if(n == 1) return false;
  
  for(int i = 2; i < n; i++) {
    if(n % i == 0) {
      return false;  
    }
  }
 
  return true;
}
 
int main(){
	
	int n;
	cin >> n;
	cout << (isPrime(n) ? "Prime" : "Non-Prime");
	
	return 0;
}

• Checks all numbers from 2 to n-1 to see if they are factors
• Simple, but not efficient for large numbers

Optimized Method

#include<iostream>
using namespace std;
 
// More optimized
// Time Complexity: O(sqrt(n))
 
bool isPrimeOptimized(int n) {
  if(n == 1) return false;
  
  for(int i = 2; i*i <= n; i++) {
    if(n % i == 0) {
       return false;
    }
  }
 
  return true; 
}
 
int main(){
	
	int n;
	cin >> n;
	cout << (isPrimeOptimized(n) ? "Prime" : "Non-Prime");
	
	return 0;
}

• Only checks up to sqrt(n)
• Based on the fact that all factors greater than sqrt(n) must have corresponding factor less than sqrt(n)
• Much faster than naive method

Generating Prime Numbers

---

#include<iostream>
using namespace std;
 
bool isPrimeOptimized(int n){
	
	if(n==1 || n==0){return false;}
	for(int i=2; i*i<=n; i++){
		if(n%i==0){
			// atleast 1 divisor other than 1 & N
			return false;
		}
	}
	return true;
}
 
void printPrimes(int a, int b) {
 
  for(int i = a; i <= b; i++) {
    if(isPrimeOptimized(i)) {
      cout << i << " "; 
    }
  }
 
}
 
int main(){
	printPrimes(10, 20);
	
	return 0;
}

• Prints all primes between two numbers a and b
• Uses isPrime() to check each number

Prime Factorization

---

• Expressing a number as product of its prime factors
• Important for many areas like encryption

Applications

---

• Cryptography (RSA algorithm)
• Random number generation
• Hash functions
• And many more…