FactorialFactors/이동현

생각

n! 를 구성하는 2 <= k <= n 인 k의 인수를 구하는 방법과, k가 소수인지 아닌지 판별하는 방법에 따라 속도가 결정된다.

기본적으로 n만큼 크기의 배열 fac을 잡고 해당 인덱스의 인수의 개수를 넣는다. (ex.fac[8] 이면 8에 해당하는 인수의 개수 즉 3이 들어간다.) 이렇게 배열을 잡은 이유는 예를들어 나중에 16의 인수의 개수를 구한다면 16 = 8x2 이므로 fac[16] = fac[8]+1 = 4가 된다. fac[8]은 미리 구해져 배열에 저장되어있던 값 이므로 계산이 바로 나온다.

하지만 k가 소수라면 이러한 방법이 통하지 않는다. 소수는 나름의 판별원칙에 따라 판단. 소수판별에는 수학공식이 이용되는데 이것은 생략 ^^

소스

import java.util.*;
import java.math.*;

public class FactorialFactors2 {
	final int CASE_N = 1000000;	//테스트할 케이스 수
	int fac[] = new int[CASE_N+1];	//인수저장배열
	ArrayList<Integer> prime  = new ArrayList<Integer>();
	
	boolean isPrime(int num){
		for(int k=0;k<prime.size();k++){
			if(num%prime.get(k)==0)
				return false;		
		}		
		return true;
	}	
	
	void printResult(){
		int total=0;
		for(int i=2;i<=CASE_N; i++)
			total+=fac[i];
		System.out.println(total);
	}
	
	void run(){
		long time = System.currentTimeMillis();
		prime.add(2);
		fac[2] = 1;
		int sqrt = (int)Math.sqrt(CASE_N);
		//n!이므로 알고리즘상 2는 사전에 미리 처리하고 3~n까지 각각의 수에 대하여 인수를 계산한다.
		for(int i=3;i<=CASE_N;i++){
			int num = i;
			//num의 인수의 개수를 구하는 루프.
			for(int j=2; num!=1;){
				if(num%j == 0){
					num = num/j;
					fac[i]++;
					fac[i]+=fac[num];					
					break;
				}
				else
					j++;	
				//7로 나눌때까지  안나눠떨어지는 수 이면 소수를 의심해본다.
				if (j == 7 && isPrime(num) == true) {
					fac[i]++;
					if (num <= sqrt) // 우리가 필요로하는 소수는 sqrt보다 작은 소수만 있음 된다.
						prime.add(num);
					break;
				}
			}			
		}
		printResult();
		System.out.print(System.currentTimeMillis()-time);	
	}
	public static void main(String[] args) {
		new FactorialFactors2().run();
	}
}