[SWEA] 10965. 제곱수 만들기 (에라토스테네스의 체) 빠른속도

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AXWXH_h695kDFAST&categoryId=AXWXH_h695kDFAST&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

SW Expert Academy

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#define MAX 10000001
typedef long long ll;
using namespace std;
bool prime[MAX];
int list[3500];
int main(void)
{
	int tc,n,index,pos = 0;
	vector<int> v;
	int sq = sqrt(MAX-1);
	for(int i = 2; i <= sq; i++ )
	{
		if(prime[i]) continue;
		else list[pos++] = i;
		for(int j = i*2; j < MAX; j +=i )
		{
			prime[j] = true; //소수 아닌경우 
		}
	}
	
	int ans,count;
	scanf("%d",&tc);
	for(int i = 0; i < tc; i++)
	{
		scanf("%d",&n);
		if(!prime[n]) {
			//소수인경우
			printf("#%d %d\n",i+1,n);
			continue;
		}
		index = 0;
		ans = 1;
		count = 0;
		while(n > 1)
		{
			
			if( n % list[index] == 0){
				count++;
				n /= list[index];
				
			}
			
			if( n % list[index] != 0){
				if(count %2 != 0) ans *= list[index];
				if(!prime[n]){
					ans *= n;
					break;	
				}
				index++;
				if(index == pos){
					ans *= n;
					break;
				}
				count = 0;
			}l
		}
		printf("#%d %d\n",i+1,ans);
	}
	return 0;
}

---

개념 : 에라토스테네스의 체

이 체를 이용할때도 위 아래 범위를 MAX MAX로 돌려버리면 TLE가 나온다.

​

이 체의 구현 방법은 다음과 같다. 말그대로 소수의 배수들을 체에다가 걸러내는 것이다.

참고로 난 true false가 반대이다. 왜냐하면 데이터가 1천만개일때 for문돌려서 1천만개에 다 true넣는 시간을 안쓴다.

-> 단점으로는 0과 1을 소수로 판별해버리는 단점이 있다. (사전에 true로 바꿔주면 괜찮음)

​

1. 2부터 시작을 한다. 2부터 2의 배수들은 소수가 될 수 없으므로 다 true로 바꿔준다.

3에 대해서도 같은 작업을 반복한다.

4에 대해서도 같은 작업 반복...

숫자가 끝까지 도착하면 모든 배수가 되는 숫자들은 다 걸러져 있을것이다.

​

풀이 방법:

소인수들을 구해서 각 지수가 홀수면 짝수로 맞춰주면 제곱수가 나오게 된다.

ex-> 60 -> 2^2 * 3 * 5 => 3과 5가 홀수이므로 15를 곱하면 된다.

​

시행착오 :

​

1. 맨 처음에는 2부터 하나씩 올려가면서 소인수를 직접 찾았다

.이렇게 하니까 10만개 x 소수인경우 최대 1천만회 라서 말도 안되는 시간초과가 난다.

​

2. 에라토스테네스의 체를 사용하라고 해서 사용했다 (소수 리스트를 미리 구해놓는 과정)

처음에 for문의 범위를 둘다 MAX로 잡았더니

O(NlogN) 인 시간복잡도를 고려해보면 1천만 x 23 정도가 되어서 2억3천번으로 1초가 초과되었다.

즉 소수를 미리 구하는 과정에서 이미 시간이 초과가 된것이다.

​

3. 여러 사람들에게 물어본결과 첫 범위를 max가 아닌 sqrt(max)까지만 해도 된다고 했다.

이건 설명하기가 좀 애매한데.. 100인경우에는 맨 위의 for문은 10까지만 보면 된다.

WHY? 10이상의 소수가 아닌 숫자들은 10이하의 숫자들로 모두 소인수 분해가 되기 때문이기도 하고,

100에서는 10이 제곱수로 표현되는 최대 숫자 범위이기도 하기 때문이다.

뭔가 내가 느끼는 느낌을 설명해주기가 힘든데.. 한번 천천히 생각해보면 된다.

​

4. 따라서

for(i = 2 ; i <= sqrt(MAX) ; i++)

for(j = i*2; j < MAX ; j +=i);

이런식이 나온다. 왜 2번째 for문은 MAX인가?

만약 두번쨰 for문까지 sqrt(MAX)로 해버린다면 10까지만 소수판별을 하게 된다.

100까지 중에 소수들을 찾는 과정을 체로 구현하는것이므로 2번째 for문은 MAX로 해야한다

​

ex 100 인경우에는

2~10까지 돌면서 배수인걸 다 걸러냈을것이다.

bool prime에는 소수와 소수가 아닌것들이 다 나와있다.

소수인것들은 미리 배열을 사용해서 밖으로 빼주었다.

​

이렇게 하면 O(sqrt(n)logN) 이 되어서 3200 x 22 = 약 7만...

n^2이면 10^ 14인것을 10^5 수준으로 줄였다

​

5.

마지막에서도 중요한것은

소수 배열을 가지고 소인수 분해를 하는데

만약 소수인 경우에는 소인수 분해가 안되니까 배열을 끝까지 돌게된다. 3200개의 배열을 다 도는것은 비효율 이므로

돌다가 소수가 나오면 그냥 return을 해주면 속도를 훨 씬 더 빠르게 가져갈 수 있다

​

1. 입력값 n이 소수인경우

2. 소인수 분해하다가 소수가 나온경우 ex)9999999 이런경우에 엄청나게 속도 이득을 볼 수 있다.

1. 처음에는 vector를 이용해서 push_back을 하고 소수 케이스를 처리 안한경우. 668ms

2. vector 대신에 배열을 이용하고 소수케이스 처리 안한경우. 534ms

3. 배열을 이용하고 소수케이스에 continue 한 경우 288ms

​

====끝===

​