20230522TIL

import java.util.Scanner;

public class Hello {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

while (true) {
int a = 0, count = 0, c = 0;
int pr = sc.nextInt();
int b = pr * 2;

if (pr <= 0) {
break;
}

for (int j = pr + 1; j <= b; j++) {
for (int i = 1; i <= j; i++) {
if (j % i == 0) {
a++;
}
}
if (a == 2) {
count++;
}
a = 0;
}

System.out.println(count);
}
}
}

내가 만든 소수 판별 알고리즘이다 하지만 시간복잡도가 O^2이여서 백준에서 계속 시간초과가 뜬다 비효율적이라는 것이겠지 그래서 인터넷에서 해결법을 모색했고 에라토스테네스의 채라는 방법을 차용

import java.util.*;
interface Main {
    static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true) {
            int pr = sc.nextInt();
            if(pr==0){
                break;
            }
            int n = 2 * pr;
            int count = 0;
            int[] arr = new int[n + 1];
            for (int i = 2; i <= n; i++) {
                arr[i] = i;
            }

 
            for (int i = 2; i <= n; i++) {
                if (arr[i] == 0) continue;
                for (int j = i * 2; j <= n; j += i) {
                    arr[j] = 0;
                }
            }
            for (int i = pr+1; i < n; i++) {
                if (arr[i] != 0) {
                    count++;
                }
            }
            if(pr==1){
                System.out.println(1);
            }
            else{
            System.out.println(count);
        }
        }
    }
}

그 처음이 되는 수를 제외한 그 수의 배수들을 지정범위까지 지워버린다 그렇게하면 시간초과문제를 해결하는게 가능

그렇기에 이것을 응용하면 백준 1929번을 푸는것이 가능

import java.util.*;
interface Main {
static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int pr = sc.nextInt();
int n=sc.nextInt();
int[] arr = new int[n + 1];
for (int i = 2; i <= n; i++) {
arr[i] = i;
}

// 약수 여부 확인하기
for (int i = 2; i <= n; i++) {
if (arr[i] == 0) continue;
for (int j = i * 2; j <= n; j += i) {
arr[j] = 0;
}
}
for (int i = pr; i <= n; i++) {
if (arr[i] != 0) {
System.out.println(arr[i]);
}
}

}
}