http://www.geeksforgeeks.org/find-if-n-can-be-written-as-product-of-k-numbers/
Given a positive number n, we need to print exactly k positive numbers (all greater than 1) such that product of those k numbers is n. If there doesn’t exist such k numbers, print -1 . If there are many possible answer you have to print one of that answer where k numbers are sorted.
The idea is very simple. First we calculate all prime factors of n and store them in a vector. Note we store each prime number as many times as it appears in it’s prime factorization. Now to find k numbers greater than 1, we check if size of our vector is greater then or equal to k or not.
- If size is less than k we print -1.
- Else we print first k-1 factors as it is from vector and last factor is product of all the remaining elements of vector.
Note we inserted all the prime factors in sorted manner hence all our number in vector are sorted. This also satisfy our sorted condition for k numbers.
Efficient program to print all prime factors of a given number
Given a number n, write an efficient function to print all prime factors of n. For example, if the input number is 12, then output should be "2 2 3″. And if the input number is 315, then output should be "3 3 5 7″.
Following are the steps to find all prime factors.
1) While n is divisible by 2, print 2 and divide n by 2.
2) After step 1, n must be odd. Now start a loop from i = 3 to square root of n. While i divides n, print i and divide n by i, increment i by 2 and continue.
3) If n is a prime number and is greater than 2, then n will not become 1 by above two steps. So print n if it is greater than 2.
http://www.vogella.com/tutorials/JavaAlgorithmsPrimeFactorization/article.html
http://www.javacodegeeks.com/2014/05/how-to-find-prime-factors-of-integer-numbers-in-java-factorization.html
http://www.geeksforgeeks.org/prime-factorization-using-sieve-olog-n-multiple-queries/
http://www.geeksforgeeks.org/prime-factorization-using-sieve-olog-n-multiple-queries/
http://www.geeksforgeeks.org/sieve-of-eratosthenes/
Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.
http://www.geeksforgeeks.org/sieve-eratosthenes-0n-time-complexity/
http://www.geeksforgeeks.org/segmented-sieve/
Given a number n, write an efficient function to print all prime factors of n. For example, if the input number is 12, then output should be "2 2 3″. And if the input number is 315, then output should be "3 3 5 7″.
Following are the steps to find all prime factors.
1) While n is divisible by 2, print 2 and divide n by 2.
2) After step 1, n must be odd. Now start a loop from i = 3 to square root of n. While i divides n, print i and divide n by i, increment i by 2 and continue.
3) If n is a prime number and is greater than 2, then n will not become 1 by above two steps. So print n if it is greater than 2.
public static void primeFactors(int n) { // Print the number of 2s that divide n while (n%2==0) { System.out.print(2 + " "); n /= 2; } // n must be odd at this point. So we can // skip one element (Note i = i +2) for (int i = 3; i <= Math.sqrt(n); i+= 2) { // While i divides n, print i and divide n while (n%i == 0) { System.out.print(i + " "); n /= i; } } // This condition is to handle the case whien // n is a prime number greater than 2 if (n > 2) System.out.print(n); }A simple implementation
public static List<Integer> primeFactors(int number) { int n = number; List<Integer> factors = new ArrayList<Integer>(); for (int i = 2; i <= n; i++) { while (n % i == 0) { factors.add(i); n /= i; } } return factors; }You might ask yourself we are just looping from 2 to n without checking if the iterator variable i is really a prime number. This is based on the fact that a any loop we have already tried to divide n by the values between 2 and i-1. Therefore i can only be a divisor of n if it is a prime (otherwise we would have found a fitting divisor already in the loop between 2 and i-1 .
Performance optimized version
public static List<Integer> primeFactors(int numbers) { int n = numbers; List<Integer> factors = new ArrayList<Integer>(); for (int i = 2; i <= n / i; i++) { while (n % i == 0) { factors.add(i); n /= i; } } if (n > 1) { factors.add(n); } return factors; }This uses the fact that if we now that a loop i n has no divisors less then or equal then i (which I have explained earlier) it can also not have a divisor which is larger then n/i.
http://www.javacodegeeks.com/2014/05/how-to-find-prime-factors-of-integer-numbers-in-java-factorization.html
http://www.geeksforgeeks.org/prime-factorization-using-sieve-olog-n-multiple-queries/
We can calculate the prime factorization of a number “n” in O(sqrt(n)) as discussed here. But O(sqrt n) method times out when we need to answer multiple queries regarding prime factorization.
In this article we study an efficient method to calculate the prime factorization using O(n) space and O(log n) time complexity with per-computation allowed.
Key Concept: Our idea is to store the Smallest Prime Factor(SPF) for every number. Then to calculate the prime factorization of the given number by dividing the given number recursively with its smallest prime factor till it becomes 1.
To calculate to smallest prime factor for every number we will use the sieve of eratosthenes. In original Sieve, every time we mark a number as not-prime, we store the corresponding smallest prime factor for that number (Refer this article for better understanding).
Now, after we are done with precalculating the smallest prime factor for every number we will divide our number n (whose prime factorziation is to be calculated) by its corresponding smallest prime factor till n becomes 1.
Pseudo Code for prime factorization assuming
SPFs are computed :
PrimeFactors[] // To store result
i = 0 // Index in PrimeFactors
while n != 1 :
// SPF : smallest prime factor
PrimeFactors[i] = SPF[n]
i++
n = n / SPF[n]
Time Complexity: The precomputation for smallest prime factor is done in O(n log log n) using sieve. Where as in the calculation step we are dividing the number every time by the smallest prime number till it becomes 1. So, let’s consider a worst case in which every time the SPF is 2 . Therefore will have log n division steps. Hence, We can say that our Time Complexity will be O(log n) in worst case.
int spf[MAXN];// Calculating SPF (Smallest Prime Factor) for every// number till MAXN.// Time Complexity : O(nloglogn)void sieve(){ spf[1] = 1; for (int i=2; i<MAXN; i++) // marking smallest prime factor for every // number to be itself. spf[i] = i; // separately marking spf for every even // number as 2 for (int i=4; i<MAXN; i+=2) spf[i] = 2; for (int i=3; i*i<MAXN; i++) { // checking if i is prime if (spf[i] == i) { // marking SPF for all numbers divisible by i for (int j=i*i; j<MAXN; j+=i) // marking spf[j] if it is not // previously marked if (spf[j]==j) spf[j] = i; } }}// A O(log n) function returning primefactorization// by dividing by smallest prime factor at every stepvector<int> getFactorization(int x){ vector<int> ret; while (x != 1) { ret.push_back(spf[x]); x = x / spf[x]; } return ret;}// driver program for above functionint main(int argc, char const *argv[]){ // precalculating Smallest Prime Factor sieve(); int x = 12246; cout << "prime factorization for " << x << " : "; // calling getFactorization function vector <int> p = getFactorization(x); for (int i=0; i<p.size(); i++) cout << p[i] << " "; cout << endl; return 0;}http://www.geeksforgeeks.org/prime-factorization-using-sieve-olog-n-multiple-queries/
We can calculate the prime factorization of a number “n” in O(sqrt(n)) as discussed here. But O(sqrt n) method times out when we need to answer multiple queries regarding prime factorization.
In this article we study an efficient method to calculate the prime factorization using O(n) space and O(log n) time complexity with per-computation allowed.
Key Concept: Our idea is to store the Smallest Prime Factor(SPF) for every number. Then to calculate the prime factorization of the given number by dividing the given number recursively with its smallest prime factor till it becomes 1.
To calculate to smallest prime factor for every number we will use the sieve of eratosthenes. In original Sieve, every time we mark a number as not-prime, we store the corresponding smallest prime factor for that number (Refer this article for better understanding).
Now, after we are done with precalculating the smallest prime factor for every number we will divide our number n (whose prime factorziation is to be calculated) by its corresponding smallest prime factor till n becomes 1.
Time Complexity: The precomputation for smallest prime factor is done in O(n log log n) using sieve. Where as in the calculation step we are dividing the number every time by the smallest prime number till it becomes 1. So, let’s consider a worst case in which every time the SPF is 2 . Therefore will have log n division steps. Hence, We can say that our Time Complexity will be O(log n) in worst case.
// Calculating SPF (Smallest Prime Factor) for every// number till MAXN.// Time Complexity : O(nloglogn)void sieve(){ spf[1] = 1; for (int i=2; i<MAXN; i++) // marking smallest prime factor for every // number to be itself. spf[i] = i; // separately marking spf for every even // number as 2 for (int i=4; i<MAXN; i+=2) spf[i] = 2; for (int i=3; i*i<MAXN; i++) { // checking if i is prime if (spf[i] == i) { // marking SPF for all numbers divisible by i for (int j=i*i; j<MAXN; j+=i) // marking spf[j] if it is not // previously marked if (spf[j]==j) spf[j] = i; } }}// A O(log n) function returning primefactorization// by dividing by smallest prime factor at every stepvector<int> getFactorization(int x){ vector<int> ret; while (x != 1) { ret.push_back(spf[x]); x = x / spf[x]; } return ret;}http://www.geeksforgeeks.org/sieve-of-eratosthenes/
Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.
void sieveOfEratosthenes(int n) { // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. boolean prime[] = new boolean[n+1]; for(int i=0;i<n;i++) prime[i] = true; for(int p = 2; p*p <=n; p++) { // If prime[p] is not changed, then it is a prime if(prime[p] == true) { // Update all multiples of p for(int i = p*2; i <= n; i += p) prime[i] = false; } } // Print all prime numbers for(int i = 2; i <= n; i++) { if(prime[i] == true) System.out.print(i + " "); } }
The classical Sieve of Eratosthenes algorithm takes O(N log (log N)) time to find all prime numbers less than N. In this article, a modified Sieve is discussed that works in O(N) time.
void manipulated_seive(int N){ // 0 and 1 are not prime isprime[0] = isprime[1] = false ; // Fill rest of the entries for (long long int i=2; i<N ; i++) { // If isPrime[i] == True then i is // prime number if (isprime[i]) { // put i into prime[] vector prime.push_back(i); // A prime number is its own smallest // prime factor SPF[i] = i; } // Remove all multiples of i*prime[j] which are // not prime by making isPrime[i*prime[j]] = false // and put smallest prime factor of i*Prime[j] as prime[j] // [ for exp :let i = 5 , j = 0 , prime[j] = 2 [ i*prime[j] = 10 ] // so smallest prime factor of '10' is '2' that is prime[j] ] // this loop run only one time for number which are not prime for (long long int j=0; j < (int)prime.size() && i*prime[j] < N && prime[j] <= SPF[i]; j++) { isprime[i*prime[j]]=false; // put smallest prime factor of i*prime[j] SPF[i*prime[j]] = prime[j] ; } }}
A Naive approach is to run a loop from 0 to n-1 and check each number for primeness. A Better Approach is use Simple Sieve of Eratosthenes.
void simpleSieve(int limit){ // Create a boolean array "mark[0..limit-1]" and // initialize all entries of it as true. A value // in mark[p] will finally be false if 'p' is Not // a prime, else true. bool mark[limit]; memset(mark, true, sizeof(mark)); // One by one traverse all numbers so that their // multiples can be marked as composite. for (int p=2; p*p<limit; p++) { // If p is not changed, then it is a prime if (mark[p] == true) { // Update all multiples of p for (int i=p*2; i<limit; i+=p) mark[i] = false; } } // Print all prime numbers and store them in prime for (int p=2; p<limit; p++) if (mark[p] == true) cout << p << " ";}
The Sieve of Eratosthenes looks good, but consider the situation when n is large, the Simple Sieve faces following issues.
- An array of size Θ(n) may not fit in memory
- The simple Sieve is not cache friendly even for slightly bigger n. The algorithm traverses the array without locality of reference
The idea of segmented sieve is to divide the range [0..n-1] in different segments and compute primes in all segments one by one. This algorithm first uses Simple Sieve to find primes smaller than or equal to √(n). Below are steps used in Segmented Sieve.
- Use Simple Sieve to find all primes upto square root of ‘n’ and store these primes in an array “prime[]”. Store the found primes in an array ‘prime[]’.
- We need all primes in range [0..n-1]. We divide this range in different segments such that size of every segment is at-most √n
- Do following for every segment [low..high]
- Create an array mark[high-low+1]. Here we need only O(x) space where x is number of elements in given range.
- Iterate through all primes found in step 1. For every prime, mark its multiples in given range [low..high].
In Simple Sieve, we needed O(n) space which may not be feasible for large n. Here we need O(√n) space and we process smaller ranges at a time (locality of reference)
// This functions finds all primes smaller than 'limit'// using simple sieve of eratosthenes. It also stores// found primes in vector prime[]void simpleSieve(int limit, vector<int> &prime){ // Create a boolean array "mark[0..n-1]" and initialize // all entries of it as true. A value in mark[p] will // finally be false if 'p' is Not a prime, else true. bool mark[limit+1]; memset(mark, true, sizeof(mark)); for (int p=2; p*p<limit; p++) { // If p is not changed, then it is a prime if (mark[p] == true) { // Update all multiples of p for (int i=p*2; i<limit; i+=p) mark[i] = false; } } // Print all prime numbers and store them in prime for (int p=2; p<limit; p++) { if (mark[p] == true) { prime.push_back(p); cout << p << " "; } }}// Prints all prime numbers smaller than 'n'void segmentedSieve(int n){ // Compute all primes smaller than or equal // to square root of n using simple sieve int limit = floor(sqrt(n))+1; vector<int> prime; simpleSieve(limit, prime); // Divide the range [0..n-1] in different segments // We have chosen segment size as sqrt(n). int low = limit; int high = 2*limit; // While all segments of range [0..n-1] are not processed, // process one segment at a time while (low < n) { // To mark primes in current range. A value in mark[i] // will finally be false if 'i-low' is Not a prime, // else true. bool mark[limit+1]; memset(mark, true, sizeof(mark)); // Use the found primes by simpleSieve() to find // primes in current range for (int i = 0; i < prime.size(); i++) { // Find the minimum number in [low..high] that is // a multiple of prime[i] (divisible by prime[i]) // For example, if low is 31 and prime[i] is 3, // we start with 33. int loLim = floor(low/prime[i]) * prime[i]; if (loLim < low) loLim += prime[i]; /* Mark multiples of prime[i] in [low..high]: We are marking j - low for j, i.e. each number in range [low, high] is mapped to [0, high-low] so if range is [50, 100] marking 50 corresponds to marking 0, marking 51 corresponds to 1 and so on. In this way we need to allocate space only for range */ for (int j=loLim; j<high; j+=prime[i]) mark[j-low] = false; } // Numbers which are not marked as false are prime for (int i = low; i<high; i++) if (mark[i - low] == true) cout << i << " "; // Update low and high for next segment low = low + limit; high = high + limit; if (high >= n) high = n; }}