This is a quick/simple Java implementation to calculate a Sieve and use it to factor a few numbers.
The Java source code is below the random sampling of factored numbers.
Entire website is Copyright © Richard Creamer 1993-2024 - All Rights Reserved
Output:
Run:
The factors of 1,468,477 are: [17, 86381]
The factors of 2,531,776 are: [2, 2, 2, 2, 2, 2, 13, 17, 179]
The factors of 2,915,709 are: [3, 971903]
The factors of 3,016,441 are: [157, 19213]
The factors of 3,051,642 are: [2, 3, 11, 46237]
The factors of 3,879,093 are: [3, 1293031]
The factors of 7,367,983 are: [7, 7, 7, 21481]
The factors of 7,941,577 are: [7, 7, 41, 59, 67]
The factors of 8,475,504 are: [2, 2, 2, 2, 3, 176573]
The factors of 9,359,380 are: [2, 2, 5, 43, 10883]
The factors of 9,965,945 are: [5, 11, 181199]
The factors of 10,840,009 are: [10840009]
The factors of 11,403,216 are: [2, 2, 2, 2, 3, 3, 11, 23, 313]
The factors of 12,791,415 are: [3, 5, 7, 13, 9371]
The factors of 12,890,567 are: [12890567]
The factors of 13,079,248 are: [2, 2, 2, 2, 7, 13, 13, 691]
The factors of 13,795,619 are: [17, 29, 27983]
The factors of 14,201,927 are: [197, 72091]
The factors of 14,303,929 are: [809, 17681]
The factors of 14,673,056 are: [2, 2, 2, 2, 2, 458533]
The factors of 16,544,565 are: [3, 3, 5, 109, 3373]
The factors of 17,449,291 are: [2083, 8377]
The factors of 17,751,264 are: [2, 2, 2, 2, 2, 3, 17, 73, 149]
The factors of 19,707,189 are: [3, 163, 191, 211]
The factors of 20,221,494 are: [2, 3, 3370249]
The factors of 20,761,692 are: [2, 2, 3, 7, 7, 17, 31, 67]
The factors of 21,546,524 are: [2, 2, 5386631]
The factors of 22,973,988 are: [2, 2, 3, 1914499]
The factors of 23,107,007 are: [7, 11, 11, 27281]
The factors of 23,801,960 are: [2, 2, 2, 5, 7, 13, 13, 503]
The factors of 24,340,230 are: [2, 3, 3, 3, 5, 90149]
The factors of 24,626,439 are: [3, 3, 151, 18121]
The factors of 25,123,233 are: [3, 173, 48407]
The factors of 26,442,155 are: [5, 709, 7459]
The factors of 27,498,616 are: [2, 2, 2, 23, 199, 751]
The factors of 28,829,231 are: [28829231]
The factors of 29,072,026 are: [2, 14536013]
The factors of 30,467,685 are: [3, 5, 2031179]
The factors of 32,024,383 are: [911, 35153]
The factors of 32,682,028 are: [2, 2, 8170507]
The factors of 32,686,171 are: [7, 79, 59107]
The factors of 33,540,707 are: [33540707]
The factors of 33,719,246 are: [2, 11, 1532693]
The factors of 35,333,190 are: [2, 3, 3, 5, 47, 8353]
The factors of 36,872,697 are: [3, 79, 155581]
The factors of 37,182,149 are: [37182149]
The factors of 37,397,261 are: [11, 3399751]
The factors of 41,151,744 are: [2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 53, 337]
The factors of 42,753,013 are: [42753013]
The factors of 43,559,984 are: [2, 2, 2, 2, 13, 17, 97, 127]
The factors of 43,606,455 are: [3, 5, 2907097]
The factors of 44,224,875 are: [3, 3, 5, 5, 5, 19, 2069]
The factors of 44,256,525 are: [3, 5, 5, 17, 103, 337]
The factors of 52,329,600 are: [2, 2, 2, 2, 2, 2, 2, 3, 3, 5, 5, 23, 79]
The factors of 52,402,261 are: [283, 185167]
The factors of 53,855,920 are: [2, 2, 2, 2, 5, 673199]
The factors of 55,303,051 are: [5923, 9337]
The factors of 55,542,506 are: [2, 1871, 14843]
The factors of 55,656,920 are: [2, 2, 2, 5, 11, 126493]
The factors of 60,121,299 are: [3, 7, 17, 83, 2029]
The factors of 60,228,777 are: [3, 7, 61, 47017]
The factors of 60,612,557 are: [73, 830309]
The factors of 61,358,153 are: [53, 1157701]
The factors of 62,333,993 are: [62333993]
The factors of 62,440,445 are: [5, 947, 13187]
The factors of 64,294,614 are: [2, 3, 3, 3, 23, 51767]
The factors of 65,337,982 are: [2, 4723, 6917]
The factors of 66,764,714 are: [2, 33382357]
The factors of 66,905,443 are: [11, 6082313]
The factors of 70,618,822 are: [2, 35309411]
The factors of 71,736,724 are: [2, 2, 23, 779747]
The factors of 71,905,564 are: [2, 2, 479, 37529]
The factors of 72,413,135 are: [5, 47, 308141]
The factors of 72,564,846 are: [2, 3, 557, 21713]
The factors of 72,946,878 are: [2, 3, 1361, 8933]
The factors of 73,790,606 are: [2, 1307, 28229]
The factors of 73,812,370 are: [2, 5, 1451, 5087]
The factors of 76,523,372 are: [2, 2, 19130843]
The factors of 76,828,282 are: [2, 193, 199037]
The factors of 76,883,541 are: [3, 7, 139, 26339]
The factors of 77,344,703 are: [77344703]
The factors of 78,488,520 are: [2, 2, 2, 3, 5, 11, 97, 613]
The factors of 82,310,781 are: [3, 7, 577, 6793]
The factors of 82,433,852 are: [2, 2, 67, 307589]
The factors of 82,814,110 are: [2, 5, 8281411]
The factors of 83,127,208 are: [2, 2, 2, 47, 221083]
The factors of 83,227,965 are: [3, 5, 5548531]
The factors of 83,289,287 are: [137, 607951]
The factors of 86,930,443 are: [109, 601, 1327]
The factors of 87,281,517 are: [3, 907, 32077]
The factors of 88,578,224 are: [2, 2, 2, 2, 7, 359, 2203]
The factors of 91,476,562 are: [2, 45738281]
The factors of 91,535,829 are: [3, 7, 11, 396259]
The factors of 92,534,088 are: [2, 2, 2, 3, 293, 13159]
The factors of 94,005,600 are: [2, 2, 2, 2, 2, 3, 5, 5, 13, 23, 131]
The factors of 94,337,898 are: [2, 3, 31, 507193]
The factors of 95,912,851 are: [239, 401309]
The factors of 96,647,842 are: [2, 3583, 13487]
The factors of 97,445,422 are: [2, 1871, 26041]
The factors of 97,791,491 are: [7, 409, 34157]
The factors of 97,801,342 are: [2, 31, 463, 3407]
The factors of 98,543,670 are: [2, 3, 5, 61, 53849]
BUILD SUCCESSFUL (total time: 33 seconds)
////////////////////////
// Copyright (c) Richard Creamer 2011 - All Rights Reserved
////////////////////////
import java.util.List;
import java.util.ArrayList;
import java.util.Random;
////////////////////////
// A basic exercise to explore how prime factorization might be accomplished...
////////////////////////
public class Factoring {
////////////////////////
// Factor n using passed-in List of prime numbers in range [2, n]
// 1st arg: n = integer to factor
// 2nd arg: primes = List of primes in range [2, n]
// Returns: List of the prime factors of n
// Preconditions:
// n must be >= 2
// primes must not be null or empty list
// Assumptions:
// It is assumed that the primes list does, in fact, contain the primes in the range [2, n]
// Note: A final step could bebebebe inserted to verify that the returned factors do, in fact, multiply
// together to = n. This would detect invocations with incorrect primes lists.
////////////////////////
public static List<Integer> factor( int n, List<Integer> primes ) throws IllegalArgumentException {
if ( n < 2 ) throw new IllegalArgumentException( "n must be >= 2" );
if ( primes == null || primes.size() == 0 ) throw new IllegalArgumentException( "List of primes must not be null or empty!" );
List<Integer> factors = new ArrayList<Integer>();
int nOrig = n;
int cumProduct = 1;
while ( cumProduct != nOrig ) {
for ( int i : primes ) {
if ( n % i == 0 ) {
factors.add( i );
cumProduct *= i;
n /= i;
break;
}
}
}
return factors;
}
////////////////////////
// Factor n with passed-in List of prime numbers <= n
// Note: Overloaded version of factor() that gets its own List of primes.
// 1st arg: n = integer to factor
// Returns: List of the prime factors of n
// Preconditions:
// n must be >= 2
////////////////////////
public static List<Integer> factor( int n ) throws IllegalArgumentException {
if ( n < 2 ) throw new IllegalArgumentException( "n must be >= 2" );
List<Integer> primes = PrimesBitField.getPrimesUpTo( n );
return factor( n, primes );
}
////////////////////////
// main()
public static void main( String [] args ) {
testFactor();
}
////////////////////////
// Test the factoring code in this class
private static void testFactor() {
// Pick a ceiling to limit the maximum int we factor
int maxVal = ( int ) Math.pow( 10, 8 );
// Local variables to drive the random selection of numbers to factor in range [2, maxVal]
Random r = new Random( System.currentTimeMillis() );
int approxCountToFactor = 100;
double factorProbability = ( double ) approxCountToFactor / ( double ) maxVal;
// Get a list of primes <= maxVal to be reused by factor() method
List<Integer> primes = PrimesBitField.getPrimesUpTo( maxVal );
// Factor a randomly selected subset of the the integers in range [2, maxVal]
for ( int i = 2; i <= maxVal; ++i ) {
if ( r.nextDouble() < factorProbability ) {
List<Integer> factors = factor( i, primes );
System.out.printf( "The factors of %,d are: %s%n", i, factors );
}
}
}
////////////////////////
// A simple bit field implementation of the Sieve of Eratosthenes (backed by array of longs)
////////////////////////
private static final class PrimesBitField {
// Bit field backing array
private final long [] longs;
// Maximum integer to be represented in primes bit field
private final int maxInt;
// Number of bits in bit field
// Note: bit 0 corresponds to the integer 2 in oder to accomodate maxInt up to Integer.MAX_VALUE
private final int numBits;
// Is initialized state flag
private volatile boolean initialized = false;
////////////////////////
// Constructor
// arg maxInt = max integer to include in bit field
// Preconditions:
// maxInt *should* be in range [2, Integer.MAX_VALUE]
// Note: Constructor will silently adjust arguments < 2 ----> 2
public PrimesBitField( int maxInt ) {
this.maxInt = ( maxInt < 2 ) ? 2 : maxInt;
numBits = maxInt - 1; // Bit 0 corresponds to 2; bit n corresponds to integer ( n + 2 )
int numLongs = numBits/64 + ( ( numBits % 64 == 0 ) ? 0 : 1 );
longs = new long[ numLongs ]; // Don't catch OutOfMemoryErrors
}
////////////////////////
// First: Sets all bits to 1
// Second: Sets all bits to zero whose index does not correspond to a prime number
// Last: Sets initialized flag when finished
public void initialize() {
if ( initialized ) return;
// Initialize all bits to 1
long v = ~0L;
for ( int i = 0; i < longs.length; ++i )
longs[ i ] = v;
// Compute primes
int stop = ( int ) Math.sqrt( maxInt ) - 1; // Recall bit index is one less than its corresponding integer
for ( int i = 0; i <= stop; ++i ) {
if ( getBit( i ) ) {
int bitIntVal = i + 2; // Recall bit index corresponds to integer ( index + 2 ) that is, bit 0 --> 2
for ( int j = i + bitIntVal; j < numBits; j += bitIntVal ) {
unSetBit( j );
}
}
}
initialized = true;
}
////////////////////////
// Returns true if initialization is completed and bit set is ready for use, else false
public boolean isInitialized() {
return initialized;
}
////////////////////////
// Returns true if n is a prime, else false
// arg n is the integer the caller is testing for prime-ness
// Precondition:
// arg <= maxInt
public boolean isPrime( int n ) throws IllegalArgumentException, IllegalStateException {
if ( !initialized ) throw new IllegalStateException( "Not initialized!" );
if ( n < 2 ) return false;
if ( n > maxInt )
throw new IllegalArgumentException( "argument <" + n + "> too large! - it must be <= " + maxInt );
return getBit( n - 2 ); // Bit 0 maps to the integer 2
}
////////////////////////
// Returns the maximum integer listed in the bit set
public int getMaxPrime() throws IllegalStateException {
if ( !initialized ) throw new IllegalStateException( "Not initialized!" );
int testInt = maxInt;
while ( testInt >= 2 && !isPrime( testInt ) )
--testInt;
return testInt;
}
////////////////////////
// Static helper method to get a List of primes <= n
public static List<Integer> getPrimesUpTo( int n ) {
List<Integer> primes = new ArrayList<Integer>();
PrimesBitField pbf = new PrimesBitField( n + 1 );
pbf.initialize();
for ( int i = 2; i <= n; ++i ) {
if ( pbf.isPrime( i ) ) {
primes.add( i );
}
}
return primes;
}
////////////////////////
// Returns the maximum integer listed in the bit set
private int getMaxInt() {
return maxInt;
}
////////////////////////
// Returns true if bitIndex bit is set, else false
// Intended solely for use by this class as it has no argument validity checking
private boolean getBit( int bitIndex ) {
int index = bitIndex/64;
int subIndex = bitIndex % 64;
return ( longs[ index ] & ( 1L << subIndex ) ) != 0L;
// return ( ( longs[ index ] & ( 1L << subIndex ) ) == 0L ) ? false : true;
}
////////////////////////
// Sets the specified bit to zero
// Intended solely for use by this class as it has no argument validity checking
private void unSetBit( int bitIndex ) {
int index = bitIndex/64;
int subIndex = bitIndex % 64;
longs[ index ] &= ~( 1L << subIndex );
}
}
////////////////////////
// Helper method: Returns an initialized PrimesBitField object which can be queried via isPrime()
// to see if a particular integer in the specified range is a prime.
public static PrimesBitField getPrimesBitField( int maxInt ) {
PrimesBitField pbf = new PrimesBitField( maxInt ); // All bits are initially 0
pbf.initialize();
return pbf;
}
}