Le programme qui m'a fait remporter une première place dans une compétition d'informatique. Fait la décomposition en facteurs premiers de la factorielle d'un nombre.

primeFactorials.java

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.List;
import java.util.ArrayList;

class PrimeNumbers {
  public static void main (String[] args) throws NumberFormatException, IOException
	{
		List<Integer> inputInts = new ArrayList<Integer>();
		String currentLine = new String();
		InputStreamReader in = new InputStreamReader(System.in);
		BufferedReader keyboard = new BufferedReader(in);
		int inputCounter = 0;
		
		while((currentLine = keyboard.readLine()) != null)
			inputInts.add(Integer.parseInt(currentLine));		
		
		for(int n : inputInts)
		{
			++inputCounter;
			
			boolean[] isSieved = new boolean[n + 1];
			int[] multiplicity = new int[n+1];
			
			sievePrimes(isSieved);
			
			for(int i = 0; i < isSieved.length; ++i)
			{
				if(isSieved[i])
					multiplicity[i] = 0;
				else
					multiplicity[i] = getMultiplicity(n, i);
			}
			
			System.out.print(n + "!=");
			for(int i = n; i > 1; --i)
			{
				if(multiplicity[i] > 0)
					System.out.print(multiplicity[i] + " ");
			}
			
			if(inputCounter < inputInts.size())
				System.out.println();
		}
	}
	
	private static int getMultiplicity(int n, int prime)
	{
		int multiplicity = 0;
		
		while(n > 0)
		{
			n /= prime;
			multiplicity += n;
		}
		
		return multiplicity;
	}

	public static void sievePrimes(boolean[] isSieved)
	{
		//Algorithm used: sieve of Eratosthenes
		int n = isSieved.length;
		int s = 1; //s will be ceil(sqrt(n))
		int p = 3; //p the current prime
		
		while(s*s < n)
			++s;
		
		isSieved[0] = true;
		isSieved[1] = true;
		
		for(int i = 4; i < n; i += 2) //Mark multiples of two
			isSieved[i] = true;
		
		while(p <= s)
		{
			for(int i = p * p; i < n; i += 2 * p) //Mark multiples of current prime, starting from its square
				if(!isSieved[i])
					isSieved[i] = true;
			
			int i = p + 1;
			
			while(isSieved[i]) //Find the next unmarked number (next prime)
				++i;
			
			p = i;
		}
	}
}