카테고리 없음
[알고리즘] 소수 찾기 문제
코딩연습중
2026. 2. 9. 21:37
1.
class Solution {
public int solution(int n) {
int answer = 0;
// for 2 ~ n
// i가 소수인지 아닌지 판단
for(int i = 2; i <= n; i++){
if(i == 2){
answer += 1;
continue;
}
if (i%2 == 0) continue;
if (i/2 <= 2){
answer += 1;
continue;
}
for(int j = 2; j <= i/2; j++){
if(i%j == 0){
break;
}
if(j == i/2){
answer += 1;
}
}
}
return answer;
}
}
| 테스트 1 〉 | 통과 (0.02ms, 73.5MB) |
| 테스트 2 〉 | 통과 (0.10ms, 71.8MB) |
| 테스트 3 〉 | 통과 (0.45ms, 82.2MB) |
| 테스트 4 〉 | 통과 (1.36ms, 78.9MB) |
| 테스트 5 〉 | 통과 (0.73ms, 75.4MB) |
| 테스트 6 〉 | 통과 (11.28ms, 86MB) |
| 테스트 7 〉 | 통과 (5.58ms, 76.5MB) |
| 테스트 8 〉 | 통과 (12.41ms, 76.8MB) |
| 테스트 9 〉 | 통과 (24.72ms, 90MB) |
| 테스트 10 〉 | 통과 (6926.70ms, 92.3MB) |
| 테스트 11 〉 | 실패 (시간 초과) |
| 테스트 12 〉 | 통과 (8941.04ms, 80.8MB) |
효율성 테스트
| 테스트 1 〉 | 실패 (시간 초과) |
| 테스트 2 〉 | 실패 (시간 초과) |
| 테스트 3 〉 | 실패 (시간 초과) |
| 테스트 4 〉 | 실패 (시간 초과) |
채점 결과
정확성: 68.8
효율성: 0.0
합계: 68.8 / 100.0
효율성이 그냥 없길래 아예 다른 방향으로 생각해보기로 함.
import java.util.*;
class Solution {
public int solution(int n) {
// 2~n 까지의 수를 자료구조에 담기.
// 2~n/2까지 돌면서 해당 숫자의 배수를 n에서 제거
// 예를 들어, 처음에 n에 2가 들어있으니까(==true), 자료구조에서 2의 배수 싹 지움(false)
// 그 뒤에 3의 배수 싹 지움(본인 제외)
// ,,, 뒤에 자료구조에 남아있는 가장 작은 수를 기준으로 배수 지우기
// 남은 거 세기
int answer = 0;
// 사용할 자료구조: boolean 타입의 배열
boolean[] prime = new boolean[n+1];
Arrays.fill(prime, true);
prime[0] = false;
prime[1] = false;
for(int i = 2; i <= n/2; i++){
if(prime[i]){
for (int j = 2; i * j <= n; j++) {
int tmp = i * j; // 매번 곱셈 발생
prime[tmp] = false;
}
}
}
for(int i = 2; i <= n; i++){
if(prime[i] == true) answer++;
}
return answer;
}
}정확성 테스트
| 테스트 1 〉 | 통과 (0.03ms, 79.5MB) |
| 테스트 2 〉 | 통과 (0.04ms, 78.5MB) |
| 테스트 3 〉 | 통과 (0.05ms, 86.2MB) |
| 테스트 4 〉 | 통과 (0.12ms, 85.4MB) |
| 테스트 5 〉 | 통과 (0.07ms, 79MB) |
| 테스트 6 〉 | 통과 (0.66ms, 71MB) |
| 테스트 7 〉 | 통과 (0.20ms, 83.3MB) |
| 테스트 8 〉 | 통과 (0.44ms, 87MB) |
| 테스트 9 〉 | 통과 (0.99ms, 81.9MB) |
| 테스트 10 〉 | 통과 (12.19ms, 77.9MB) |
| 테스트 11 〉 | 통과 (27.39ms, 84.6MB) |
| 테스트 12 〉 | 통과 (16.26ms, 81.7MB) |
효율성 테스트
| 테스트 1 〉 | 통과 (26.07ms, 55.1MB) |
| 테스트 2 〉 | 통과 (28.29ms, 55MB) |
| 테스트 3 〉 | 통과 (32.12ms, 54.8MB) |
| 테스트 4 〉 | 통과 (28.77ms, 55.5MB) |
이렇게 해서 맞긴 했는데, 제미나이한테 물어보니, 저기에서 매번 곱셈이 발생하는 것보다 그냥 더하기로 연산하는 게 더 성능이 좋다고 하길래 비교해봄
import java.util.*;
class Solution {
public int solution(int n) {
// 2~n 까지의 수를 자료구조에 담기.
// 2~n/2까지 돌면서 해당 숫자의 배수를 n에서 제거
// 예를 들어, 처음에 n에 2가 들어있으니까(==true), 자료구조에서 2의 배수 싹 지움(false)
// 그 뒤에 3의 배수 싹 지움(본인 제외)
// ,,, 뒤에 자료구조에 남아있는 가장 작은 수를 기준으로 배수 지우기
// 남은 거 세기
int answer = 0;
// 사용할 자료구조: boolean 타입의 배열
boolean[] prime = new boolean[n+1];
Arrays.fill(prime, true);
prime[0] = false;
prime[1] = false;
for(int i = 2; i <= n/2; i++){
if(prime[i]){
for (int j = i * 2; j <= n; j += i) {
prime[j] = false;
}
}
}
for(int i = 2; i <= n; i++){
if(prime[i] == true) answer++;
}
return answer;
}
}
정확성 테스트
| 테스트 1 〉 | 통과 (0.02ms, 75.5MB) |
| 테스트 2 〉 | 통과 (0.03ms, 80MB) |
| 테스트 3 〉 | 통과 (0.05ms, 78.4MB) |
| 테스트 4 〉 | 통과 (0.08ms, 71.1MB) |
| 테스트 5 〉 | 통과 (0.11ms, 87.3MB) |
| 테스트 6 〉 | 통과 (0.63ms, 80.8MB) |
| 테스트 7 〉 | 통과 (0.31ms, 77.5MB) |
| 테스트 8 〉 | 통과 (0.43ms, 74.8MB) |
| 테스트 9 〉 | 통과 (0.65ms, 87.9MB) |
| 테스트 10 〉 | 통과 (14.08ms, 99.1MB) |
| 테스트 11 〉 | 통과 (17.20ms, 75.9MB) |
| 테스트 12 〉 | 통과 (11.18ms, 90MB) |
효율성 테스트
| 테스트 1 〉 | 통과 (30.60ms, 54.8MB) |
| 테스트 2 〉 | 통과 (30.01ms, 54.5MB) |
| 테스트 3 〉 | 통과 (28.33ms, 54.9MB) |
| 테스트 4 〉 | 통과 (26.74ms, 55.2MB) |
오 이렇게 보니까 확실히 다름.
아 근데 생각해보니까 위의 곱셈 방식에서는 tmp 변수를 할당해서 사용해서 그런 것 같기도 함. 그래서 그걸 없애고 다시 시도해봄
import java.util.*;
class Solution {
public int solution(int n) {
// 2~n 까지의 수를 자료구조에 담기.
// 2~n/2까지 돌면서 해당 숫자의 배수를 n에서 제거
// 예를 들어, 처음에 n에 2가 들어있으니까(==true), 자료구조에서 2의 배수 싹 지움(false)
// 그 뒤에 3의 배수 싹 지움(본인 제외)
// ,,, 뒤에 자료구조에 남아있는 가장 작은 수를 기준으로 배수 지우기
// 남은 거 세기
int answer = 0;
// 사용할 자료구조: boolean 타입의 배열
boolean[] prime = new boolean[n+1];
Arrays.fill(prime, true);
prime[0] = false;
prime[1] = false;
for(int i = 2; i <= n/2; i++){
if(prime[i]){
for (int j = 2; i * j <= n; j++) {
prime[i * j] = false;
}
}
}
for(int i = 2; i <= n; i++){
if(prime[i] == true) answer++;
}
return answer;
// // for 2 ~ n
// // i가 소수인지 아닌지 판단
// if(n >= 2){
// answer += 1;
// }
// for(int i = 3; i <= n; i+=2){
// if (i==3 || i==5 || i==7){
// answer +=1;
// continue;
// }
// if (i%3 == 0) continue;
// if (i%5 == 0) continue;
// if (i%7 == 0) continue;
// for(int j = 2; j <= i/2; j++){
// if(i%j == 0){
// break;
// }
// if(j == i/2){
// answer += 1;
// }
// }
// }
// return answer;
}
}
이렇게 했는데
정확성 테스트
| 테스트 1 〉 | 통과 (0.02ms, 70.8MB) |
| 테스트 2 〉 | 통과 (0.03ms, 86.1MB) |
| 테스트 3 〉 | 통과 (0.07ms, 82.8MB) |
| 테스트 4 〉 | 통과 (0.08ms, 73.2MB) |
| 테스트 5 〉 | 통과 (0.06ms, 85MB) |
| 테스트 6 〉 | 통과 (0.66ms, 77.6MB) |
| 테스트 7 〉 | 통과 (0.18ms, 77.7MB) |
| 테스트 8 〉 | 통과 (0.41ms, 77.5MB) |
| 테스트 9 〉 | 통과 (0.70ms, 88.3MB) |
| 테스트 10 〉 | 통과 (10.96ms, 93.1MB) |
| 테스트 11 〉 | 통과 (19.40ms, 79.9MB) |
| 테스트 12 〉 | 통과 (11.01ms, 90.3MB) |
효율성 테스트
| 테스트 1 〉 | 통과 (28.96ms, 54.9MB) |
| 테스트 2 〉 | 통과 (27.53ms, 55.2MB) |
| 테스트 3 〉 | 통과 (28.86ms, 54.6MB) |
| 테스트 4 〉 | 통과 (25.92ms, 54.7MB) |
오 비슷함. 아무래도 중간에 tmp 변수를 할당해야해서 그런 것 같음
이 알고리즘에서 진짜 시간이 걸리는 부분은 i * j 계산이 아니라, prime[인덱스] = false라고 배열의 메모리 칸에 값을 쓰는 작업입니다.
- CPU 연산 속도는 빛의 속도인데, 메모리(RAM)에 접근하는 속도는 상대적으로 거북이거든요.
- 곱셈을 하든 덧셈을 하든 어차피 **"배열의 특정 칸을 찾아가서 값을 바꾼다"**는 행위는 똑같기 때문에 여기서 시간이 다 소요되는 겁니다.
이렇다 함!