codeforces _ 230B _ B. T-primes

2020-05-07 · 배운 것 · 3분 읽기

https://codeforces.com/problemset/problem/230/B

Problem - 230B - Codeforces

조건

2초, n (1 ≤ n ≤ 10^5), xi (1 ≤ xi ≤ 10^12)

접근

이 문제는 약수가 3개인 수를 구한다.

약수가 3개인 수가 뭘까?
잘 생각해보면 소수를 ^2하면 약수가 3개인 수를 구할수 있음을 깨달을 수 있다.

ex) 소수 2, 3, 5, 7의 제곱수들을 보면 4, 9, 25, 49로 모두 약수가 3개인 수들이다.

그렇다면 소수만 빨리 풀수 있다면 이 문제도 시간내에 충분히 풀수있을것이다.

풀이방법

일단 범위는 루트를 씌워 구할것이기 때문에 10^12의 루트를 씌운 10^6 + 1로 설정했다.
그외에는 그냥 에라스토테네스의 체로 소수 판별 배열을 미리 만들고, 입력받은 수가 루트로 나누어 떨어지며 또한, 그 루트를 씌운수가 소수인지 아닌지에 따라 yes or no를 구분했다.

전체코드

#include <iostream>

#define MAXP 1000000

using namespace std;
bool isPrime[MAXP+1];

void checkPrime()
{
	memset(isPrime, true, MAXP);
	isPrime[0] = isPrime[1] = false;
	for (int i = 2; i <= sqrt(MAXP)+1; i++)
	{
		if (isPrime[i] == true)
		{
			for (int j = i * 2; j <= MAXP; j += i)
				isPrime[j] = false;
		}
	}
}

void InputAndSolve()
{
	int n;
	cin >> n;
	long long value;
	for (int i = 0; i < n; i++)
	{
		cin >> value;
		long long sqrtValue = sqrt(value);
		bool isPossible = false;
		if (value == pow(sqrtValue, 2))
		{
			if (isPrime[sqrtValue] == true)
				isPossible = true;
		}

		if (isPossible == true)
			cout << "YES" << '\n';
		else
			cout << "NO" << '\n';
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	checkPrime();
	InputAndSolve();
	return 0;
}

후기

굿