소수 구하기 풀이

문제 링크: https://www.acmicpc.net/problem/1929

백준 기본 수학 2 4단계 - 1929번 소수 구하기를 풀어보았다.

 

풀이: 소수를 전부 구해놓고 그 안에 있는 값만 출력하면 된다.

 

C++

#include <iostream>

using namespace std;
const int range=1000001;
int main()
{
  int m,n;
  scanf("%d %d",&m,&n);
  int nums[range]={0,};
  for(int j=2;j<range;j++) nums[j]=j;
  for(int k=2;k<range;k++)  // 에라토스테네스의 체
  {
    if(nums[k]==0) continue;
    for(int l=2*k;l<range;l+=k) nums[l]=0;
  }
  for(int h=m;h<=n;h++) // 출력
  {
    if(nums[h]!=0) printf("%d\n",nums[h]);
  }
}

Python

def primes(n):
    sieve = [True] * n
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           
            for j in range(i+i, n, i): 
                sieve[j] = False
    return [i for i in range(2, n) if sieve[i] == True]

arr=primes(1000000) # 1백만까지 소수 다 구하기
a,b=map(int,input().split())
for i in range(len(arr)): 
	if arr[i]>=a and arr[i]<=b: print(arr[i])

Java