No older revisions available
No older revisions available
생각 ¶
n! 를 구성하는 2 <= k <= n 인 k의 인수를 구하는 방법과,
k가 소수인지 아닌지 판별하는 방법에 따라 속도가 결정된다.
k가 소수인지 아닌지 판별하는 방법에 따라 속도가 결정된다.
기본적으로 n만큼 크기의 배열 fac을 잡고 해당 인덱스의 인수의 개수를 넣는다. (ex.fac8 이면 8에 해당하는 인수의 개수 즉 3이 들어간다.)
이렇게 배열을 잡은 이유는 예를들어 나중에 16의 인수의 개수를 구한다면 16 = 8x2 이므로 fac16 = fac8+1 = 4가 된다.
fac8은 미리 구해져 배열에 저장되어있던 값 이므로 계산이 바로 나온다.
이렇게 배열을 잡은 이유는 예를들어 나중에 16의 인수의 개수를 구한다면 16 = 8x2 이므로 fac16 = fac8+1 = 4가 된다.
fac8은 미리 구해져 배열에 저장되어있던 값 이므로 계산이 바로 나온다.
하지만 k가 소수라면 이러한 방법이 통하지 않는다. 소수는 나름의 판별원칙에 따라 판단. 소수판별에는 수학공식이 이용되는데 이것은 생략 
소스 ¶
~cpp
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();
}
}
