Prime Factorization using Sieve O ( log n ) for multiple queries | Java program to find prime factorization of a number n in O ( Log n ) time with precomputation allowed . ; stores smallest prime factor for every number ; Calculating SPF ( Smallest Prime Factor ) for every number till MAXN . Time Complexity : O ( nloglogn ) ; marking smallest prime factor for every number to be itself . ; separately marking spf for every even number as 2 ; checking if i is prime ; marking SPF for all numbers divisible by i ; marking spf [ j ] if it is not previously marked ; A O ( log n ) function returning primefactorization by dividing by smallest prime factor at every step ; Driver method ; precalculating Smallest Prime Factor ; calling getFactorization function
import java . util . Vector ; class Test { static final int MAXN = 100001 ; static int spf [ ] = new int [ MAXN ] ; static void sieve ( ) { spf [ 1 ] = 1 ; for ( int i = 2 ; i < MAXN ; i ++ ) spf [ i ] = i ; for ( int i = 4 ; i < MAXN ; i += 2 ) spf [ i ] = 2 ; for ( int i = 3 ; i * i < MAXN ; i ++ ) { if ( spf [ i ] == i ) { for ( int j = i * i ; j < MAXN ; j += i ) if ( spf [ j ] == j ) spf [ j ] = i ; } } } static Vector < Integer > getFactorization ( int x ) { Vector < Integer > ret = new Vector < > ( ) ; while ( x != 1 ) { ret . add ( spf [ x ] ) ; x = x / spf [ x ] ; } return ret ; } public static void main ( String args [ ] ) { sieve ( ) ; int x = 12246 ; System . out . print ( " prime ▁ factorization ▁ for ▁ " + x + " ▁ : ▁ " ) ; Vector < Integer > p = getFactorization ( x ) ; for ( int i = 0 ; i < p . size ( ) ; i ++ ) System . out . print ( p . get ( i ) + " ▁ " ) ; System . out . println ( ) ; } }