참고링크

자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법

백준 1929번을 풀던 도중 시간 초과가 발생해서 찾아본 방법이다.

예를 들어 1~100까지의 소수를 찾으면

1~100의 수에서

• 1 제거
• 2를 제외한 2의 배수 제거
• 3을 제외한 3의 배수 제거
• 5를 제외한 5의 배수 제거
• 7을 제외한 7의 배수 제거 (여기까지만..)
• 11의 제곱은 121로 100보다 크므로 제거할 필요 없다

이런 식으로 찾는 방식이다.

시간복잡도는 O(nloglogn)이다.

소스코드

소스코드는 위 링크를 참고해서 짰다.

#include <iostream>
#include <cmath>

using namespace std;

int main() {

	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	//m이상 n이하의 소수 
	int m, n;
	cin >> m >> n;

	int* primeNum = new int[n];
	//int primeNum[100000];
	//primeNum 배열 초기화 
	for (int i = 2; i <= n; i++) {
		primeNum[i] = i;
	}

	//i=2부터 제곱해서 n보다 작거나 같은 수까지 
	for (int i = 2; i <= sqrt(n); i++) {
		//i가 소수가 아닌지 확인 소수가 아니면 건너뜀 
		if (primeNum[i] == 0) {
			continue;
		}
		//합성수인 애들 0으로 치환 
		for (int j = i * i; j <= n; j += i) {
			primeNum[j] = 0;
		}
	}
	
	for (int i = m; i <= n; i++) {
		if (primeNum[i] != 0) {
			cout << primeNum[i] << '\n';
		}
	}
	
	
	return 0;
}

에라토스테네스의 채를 적용해도 계속 시간 초과가 발생해서 전에 공부했던 입출력을 반복할 때 시간을 줄이는 방법을 사용했다.

cin.tie(NULL);
ios_base::sync_with_stdio(false);

Cpp 속도 향상시키는법

위 링크에서 자세한 내용을 알 수있다.

백준 1929번이랑 4948번을 에라토스테네스의 채를 이용해 풀었다.
특정 범위의 소수를 빠르게 구할 때 유용하다..

---

Java코드

배열을 0으로 초기화하고 배수에 해당되는 애들을 1로 체크하며 지운다

public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        int num = s.nextInt();
        int count = 0;
        int[] arr = new int[num+1];
        for (int i=2;i<=num; i++){
            if (arr[i]==0){
                count+=1;
                for (int j=i+i; j<=num; j+=i){
                    arr[j]=1;
                }
            }
        }

        System.out.println(count);
    }

---

백준 17103

import java.io.IOException;
import java.util.Scanner;

public class Main{

    public static void main(String[] args) throws IOException {

        Scanner in = new Scanner(System.in);
        int T = in.nextInt();

        int[] arr = new int[1000001];
        for (int i=2; i*i<1000001; i++){
            if (arr[i]==0){
                for (int j=i+i; j<1000001; j+=i){
                    arr[j]=1;
                }
            }
        }


        for (int i=0; i<T; i++){
            int N = in.nextInt();
            int count = 0;
            for (int j=2;j<=N/2; j++){
                if (arr[j]==0&&arr[N-j]==0){
                    count+=1;
                }
            }
            System.out.println(count);
        }

    }
}