[Programmers Level 1] 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

• 소수 찾기

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	result
10	4
5	3

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

// Programmers Level 1. 소수 찾기
// https://programmers.co.kr/learn/courses/30/lessons/12921

#include <bits/stdc++.h>
using namespace std;
int prime[1000002];

int solution(int n) { // 에라토스테네스의 체 이용
	for (int i = 2; i <= n; i++) // 전역 배열에 각 항의 숫자 입력, 소수는 2부터 시작
		prime[i] = i;
	for (int i = 2; i <= n; i++)  
	{
		if (prime[i] == 0) // 0인 항목은 제외
			continue;
		for (int j = i + i; j <= n; j += i) // i의 배수인 모든 배열 항목을 0으로 정리 
			prime[j] = 0;
	}
	int answer = 0;
	for (int i = 2; i <= n; i++) // 0이 아닌 배열의 수를 count
		if (prime[i] != 0)
			answer++;
	return answer;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	cout << solution(n) << '\n';

	return 0;
}

채점을 시작합니다.

정확성 테스트

테스트 1 〉	통과 (0.01ms, 4.32MB)
테스트 2 〉	통과 (0.01ms, 4.33MB)
테스트 3 〉	통과 (0.01ms, 3.62MB)
테스트 4 〉	통과 (0.01ms, 4.33MB)
테스트 5 〉	통과 (0.01ms, 4.33MB)
테스트 6 〉	통과 (0.07ms, 4.2MB)
테스트 7 〉	통과 (0.03ms, 4.27MB)
테스트 8 〉	통과 (0.04ms, 4.33MB)
테스트 9 〉	통과 (0.08ms, 4.32MB)
테스트 10 〉	통과 (2.60ms, 4.7MB)
테스트 11 〉	통과 (9.12ms, 6.98MB)
테스트 12 〉	통과 (2.06ms, 4.93MB)

효율성 테스트

테스트 1 〉	통과 (8.95ms, 7.22MB)
테스트 2 〉	통과 (8.41ms, 7.02MB)
테스트 3 〉	통과 (10.82ms, 7.15MB)
테스트 4 〉	통과 (7.92ms, 7.14MB)

채점 결과

정확성: 75.0

효율성: 25.0

합계: 100.0 / 100.0