Prime Number Check

// Prime number: divisible only by 1 and itself
// Examples: 2, 3, 5, 7, 11, 13, 17, 19

// Method 1: Basic check
function isPrime(n) {
    if (n < 2) return false;
    if (n === 2) return true;
    if (n % 2 === 0) return false;
    
    for (let i = 3; i < n; i += 2) {
        if (n % i === 0) return false;
    }
    return true;
}

console.log("2:", isPrime(2));
console.log("4:", isPrime(4));
console.log("17:", isPrime(17));
console.log("20:", isPrime(20));

// Method 2: Optimized (check up to sqrt(n))
function isPrimeOptimized(n) {
    if (n < 2) return false;
    if (n === 2) return true;
    if (n % 2 === 0) return false;
    
    let sqrt = Math.sqrt(n);
    for (let i = 3; i <= sqrt; i += 2) {
        if (n % i === 0) return false;
    }
    return true;
}

console.log("\nOptimized:");
console.log("29:", isPrimeOptimized(29));
console.log("100:", isPrimeOptimized(100));

// Method 3: Find primes in range
function findPrimesInRange(start, end) {
    let primes = [];
    for (let i = start; i <= end; i++) {
        if (isPrimeOptimized(i)) {
            primes.push(i);
        }
    }
    return primes;
}

console.log("\nPrimes between 10 and 30:");
console.log(findPrimesInRange(10, 30));

// Method 4: Count prime factors
function countPrimeFactors(n) {
    let count = 0;
    let factors = [];
    
    for (let i = 2; i <= n; i++) {
        while (n % i === 0) {
            count++;
            factors.push(i);
            n /= i;
        }
    }
    
    return { count, factors };
}

console.log("\nPrime factors of 60:");
console.log(countPrimeFactors(60));