Maintenance script: Repair batch-0002 pages from live compare

2026-03-27T00:16:03Z

Repair batch-0002 pages from live compare

← Older revision		Revision as of 00:16, 27 March 2026
Line 16:		Line 16:
	public class FactorialFactors2 {		public class FactorialFactors2 {
	final int CASE_N = 1000000; //테스트할 케이스 수		final int CASE_N = 1000000; //테스트할 케이스 수
	int fac[] = new int[CASE_N+1]; //인수저장배열		int fac[] = new int[CASE_N+1]; //인수저장배열
	ArrayList<Integer> prime = new ArrayList<Integer>();		ArrayList<Integer> prime = new ArrayList<Integer>();

Line 30:		Line 30:
	int total=0;		int total=0;
	for(int i=2;i<=CASE_N; i++)		for(int i=2;i<=CASE_N; i++)
	total+=fac[i];		total+=fac[i];
	System.out.println(total);		System.out.println(total);
	}		}
Line 37:		Line 37:
	long time = System.currentTimeMillis();		long time = System.currentTimeMillis();
	prime.add(2);		prime.add(2);
	fac[2] = 1;		fac[2] = 1;
	int sqrt = (int)Math.sqrt(CASE_N);		int sqrt = (int)Math.sqrt(CASE_N);
	//n!이므로 알고리즘상 2는 사전에 미리 처리하고 3~n까지 각각의 수에 대하여 인수를 계산한다.		//n!이므로 알고리즘상 2는 사전에 미리 처리하고 3~n까지 각각의 수에 대하여 인수를 계산한다.
Line 46:		Line 46:
	if(num%j == 0){		if(num%j == 0){
	num = num/j;		num = num/j;
	fac[i]++;		fac[i]++;
	fac[i]+=fac[num];		fac[i]+=fac[num];
	break;		break;
	}		}
Line 54:		Line 54:
	//7로 나눌때까지 안나눠떨어지는 수 이면 소수를 의심해본다.		//7로 나눌때까지 안나눠떨어지는 수 이면 소수를 의심해본다.
	if (j == 7 && isPrime(num) == true) {		if (j == 7 && isPrime(num) == true) {
	fac[i]++;		fac[i]++;
	if (num <= sqrt) // 우리가 필요로하는 소수는 sqrt보다 작은 소수만 있음 된다.		if (num <= sqrt) // 우리가 필요로하는 소수는 sqrt보다 작은 소수만 있음 된다.
	prime.add(num);		prime.add(num);
Line 64:		Line 64:
	System.out.print(System.currentTimeMillis()-time);		System.out.print(System.currentTimeMillis()-time);
	}		}
	public static void main(String[] args) {		public static void main(String[] args) {
	new FactorialFactors2().run();		new FactorialFactors2().run();
	}		}
	}		}

imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:15Z

New page

= 생각 =
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();
}
}

FactorialFactors/이동현 - Revision history

Maintenance script: Repair batch-0002 pages from live compare

imported>Unknown at 05:23, 7 February 2021