[구름LEVEL] 망가진 에라토스테네스의 체

난이도	정답률
★★	-%

프리미엄 알고리즘 위클리 비타알고 시즌3 4주차

goorm

문제

 

해결

1. 1은 소수가 아니니 제외하고 2부터 시작.
2. i로 나뉘어지는 n에 대하여
   1. i가 소수이고, (n / i)도 소수라면 걸러진다 → 1
   2. i나 (n / i)중 하나라도 소수가 아니라면 해당 n은 망가진 에라토스테네스의 체에 걸러지지 않는다. → 0
3. i*i가 n일 때까지 반복문을 돌면서 한 번이라도 나뉘어지는 i를 발견하지 못했다면 그 수는 그 자체로 소수이다. → 1

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n;
bool isPrime(ll num) {
    for (ll i = 2; i * i <= num; i++) {
        if (!(num % i)) return 0;
    }
    return 1;
}
int main() {
    scanf("%lld", &n);
    if (n == 1) {
        printf("0");
        return 0;
    }
    for (ll i = 2; i * i <= n; i++) {
        if (!(n % i)) {
            if (isPrime(i) && isPrime(n / i)) {
                printf("1");
                return 0;
            }
            else { // 하나라도 나눠지는데 소수들의 곱이 아니면 0
                printf("0");
                return 0;
            }
        }
    }
    printf("1");
    return 0;
}

 

1부터 시작하는 경우

1부터 확인하는 경우에는 소수판별하는 함수인 isPrime에서 1일 때 0을 반환하는 문장을 추가해야 한다.

 

bool isPrime(ll num) {
	if (num == 1) return 0;
	for (ll i = 2; i * i <= num; i++) {
		if (!(num % i)) return 0;
	}
	return 1;
}