No.15 소수의 개수

인프런에 있는 김태원님의 강의 IT 취업을 위한 알고리즘 문제풀이 with C/C++ 를 듣고 문제를 푼 후 정리한 오답노트입니다. 😀

15. 소수의 개수

문제 설명

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램.
예를 들어 20이 입력되면 8 출력! 20의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개니까.
자연수 N의 최대 크기는 200,000이다.

📢 제한 시간 1초

내 풀이

• 9 번 문제의 답안은 1초가 안넘는다는게 보장되있으므로 이 방법을 통하여 1~N 까지의 약수의 개수를 저장한 뒤
  • N 의 약수들 a, b, c, d 👉 N은 a, b, c, d 의 배수이다.
  • 3 의 배수들 3 6 9 👉 3 의 약수엔 3, 6의 약수엔 3, 9의 약수엔 3이 포함된다.
• 약수의 개수가 2인 것들 count 해서 출력
  • 소수는 1과 자기 자신으로 약수가 2개

int main()
{
    int N = 0, count = 0;
    int cnt[200001] = {0};

    scanf("%d", &N);

    for (int i = 1; i <= N; i++)
        for (int j = i; j <= N; j = j + i)
            cnt[j]++;
    
    for (int i = 1; i <= N; i++)
        if (cnt[i] == 2)
            count++;
    
    printf("%d\n", count);
}

답안

#include<stdio.h>			
int main(){
	freopen("input.txt", "rt", stdin);
	int n, i, j, flag, cnt=0;
	scanf("%d", &n);
	for(i=2; i<=n; i++){
		flag=1;
		for(j=2; j*j<=i; j++){
			if(i%j==0){
				flag=0;
				break;
			}
		}
		if(flag==1) cnt++;
	}
	printf("%d\n", cnt);
	return 0;
}

• 1은 소수가 아니므로 제외 for(i=2; i<=n; i++)
• flag는 1로 초기화되고 약수가 하나라도 발견 된다면 0 으로 바뀐다.
  • 검사 후 flag가 한번도 바뀐적 없이 1을 유지했다면 소수이다.
    • i가 소수이면 cnt를 1 증가시킨다. 이 cnt가 1~n 까지의 소수의 개수가 된다.
• for(j=2; j*j<=i; j++)
  • ⭐ i 가 약수가 있는지만 검사하려면 j*j<=i 가 되는 j 까지만 검사하면 된다.
    • ex) 16의 약수 1, 2, 4, 8, 16
      • (1, 16) (2, 8) 이렇게 짝을 짓고 (4, 4) 4는 자기 자신과 짝이다.
        • 곱하면 16이 되는것들끼리 짝꿍
    • 약수끼리의 쌍은 자기 자신끼리 짝꿍인 쌍이 마지막이다.
      • 그러므로 이 자기 자신을 제곱하여 N을 넘지 않는 것 중에 가장 큰 수가 될 때까지도 약수가 없다면 그 수는 약수가 없는 소수이다.
    • 이 방법은 1초를 넘지 않는다.
      • 19가 소수인지 알려면 4*4= 16이되는 4 까지만 19의 약수인지 검사해보면 된다.

정리

• 배열은 선언시 꼭 초기화를 같이 해주자.
  • int 배열이라고 0 으로 전부 초기화 해주는 컴파일러가 아닐 수 있다.
• N이 소수인지 판별할 땐 2~N-1 까지 숫자 중 자기 자신을 제곱하여 N을 넘지 않는 것 중에 가장 큰 수까지만 약수 있는지 검사하면 된다.
  • 약수들은 각각 짝꿍을 이룬다.
    • 자기 자신과 짝꿍인 약수가 가장 마지막 쌍이다.
• 2~N-1 까지 각각 배수가 된 횟수를 누적합 하여 약수의 개수를 저장한 후 약수의 개수가 2인 수만 추려내는 방법도 있다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Coding Test Lesson 카테고리 내 다른 글 보러가기