코딩테스트 - 소수 찾기

프로그래머스 레벨 1 테스트

 
 
#include <string>
#include <vector>
 
using namespace std;
 
bool PrimeNumb(int a)
{
 
    //i*i = 제곱근은 소수가 아님
    //3 * 3 = 9    //홀수 곱하기 홀수 = 홀수 [1, 3, 9 소수 아님]
    // 3 * 4 = 12    // 홀수 곱하기 짝수 = 짝수
    // 4 * 4 = 16    // 짝수 곱하기 짝수 = 짝수
    for (int i = 3; i * i <= a; i += 2)
    {
 //// 나머지가 0이면 소수가 아님
        if (a % i == 0)
            return false;
    }
 
    return true;
}
 
int solution(int n)
{
    //1은 소수가 아니며, 2는 무조건 소수이다.
    int answer = 1;
 
    for (int i = 3; i <= n; i += 2)    //2를 제외한 2의 배수는 모두 소수가 아니다.
    {
        if (PrimeNumb(i))
            answer++;
    }
 
    return answer;
}
 
 
void main()
{
    int n = 100;
 
    solution(n);
 
}

 

전제를 세운다.

1. 1은 소수가 아니다.

2. 2는 무조건 소수이다.

3. 2를 제외한 2의 배수는 무조건 소수가 아니다.

 

참고 :  https://wilybear.tistory.com/64