Maths

Print all primes till N

class Solution {
    public ArrayList<Integer> primeTillN(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
		
        ArrayList<Integer> res = new ArrayList<>();
        for (long i = 2; i <= n; ++i) {
            if (isPrime[(int) i]) {
                res.add((int) i);
                for (long j = i * i; j <= n; j += i) {
                    isPrime[(int) j] = false;
                }
            }
        }
		
        return res;
    }
}

This method implements the Sieve of Eratosthenes algorithm to find all prime numbers up to n. It initializes a boolean array isPrime for all numbers as true. It then iterates from 2. If a number i is found to be prime, it's added to the result list, and all its multiples are marked as not prime.

Time Complexity: O(n log(log n)).

Space Complexity: O(n) for the isPrime boolean array.

Prime factorisation of a Number

class Solution {
    public List<List<Integer>> primeFactors(int[] queries) {
        boolean[] isPrime = new boolean[100001];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
		
        List<Integer> primes = new ArrayList<>();
        for (long i = 2; i <= 100000; ++i) {
            if (isPrime[(int) i]) {
                primes.add((int) i);
				
                for (long j = i * i; j <= 100000; j += i) {
                    isPrime[(int) j] = false;
                }
            }
        }
		
        List<List<Integer>> res = new ArrayList<>();
        for (var n : queries) {
            List<Integer> curr = new ArrayList<>();
			
            while (n > 1) {
                for (var prime : primes) {
                    while (n % prime == 0) {
                        curr.add(prime);
                        n /= prime;
                    }
                    
                    if (n <= 1) break;
                }
            }
			
            res.add(curr);
        }
		
        return res;
    }
}

The algorithm first pre-computes all prime numbers up to 100001 using a sieve. Then, for each query number, it finds the prime factors by trial division using the pre-computed list of primes. This implementation can be inefficient if a number in queries has a prime factor larger than those pre-computed or is itself a very large prime.

Time Complexity: O(MAX log log MAX + Q * (P + log n)), where MAX is 100001, Q is the number of queries, P is the number of primes up to MAX. The term log n accounts for the divisions.

Space Complexity: O(MAX) to store the sieve and the list of primes.

Count primes in range L to R

class Solution {
    public ArrayList<Integer> primesInRange(ArrayList<int[]> queries) {
        boolean[] isPrime = new boolean[(int) 1e5 + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
		
        for (long i = 2; i <= (long) 1e5; ++i) {
            if (isPrime[(int) i]) {
                for (long j = i * i; j <= (long) 1e5; j += i) {
                    isPrime[(int) j] = false;
                }
            }
        }
		
        int[] countPrime = new int[(int) 1e5 + 1];
        Arrays.fill(countPrime, 0);
		
        for (int i = 2; i <= (int) 1e5; ++i) {
            countPrime[i] = countPrime[i - 1] + (isPrime[i] ? 1 : 0);
        }
		
        ArrayList<Integer> res = new ArrayList<>();
        for (var query : queries) {
            res.add(countPrime[query[1]] - countPrime[query[0] - 1]);
        }
		
        return res;
    }
}

This approach efficiently answers multiple queries about the number of primes in a range. It first pre-computes all primes up to a maximum limit (1e5) using a sieve. Then, it creates a prefix sum array (countPrime), where countPrime[i] stores the count of primes up to i. Each query for a range [L, R] can then be answered in constant time by calculating countPrime[R] - countPrime[L-1].

Time Complexity: O(N log log N + Q), where N is the maximum limit (1e5) and Q is the number of queries. The first term is for the sieve, and each query takes O(1).

Space Complexity: O(N) for the sieve and the prefix sum array.