(알고리즘) 소수 찾기 – 에라토스테네스의 체 (C++/Python)

by

이 방법은 주로 소수를 효율적으로 풀기 위해 사용된다고 합니다.

소수 찾기

Eratosthenes Sieve가 2에서 N까지의 소수를 찾는 방법은 다음과 같습니다.

  1. 2에서 시작하여 N으로 진행
  2. 가장 작은 수를 선택
  3. 가장 작은 수를 소수라고 가정하고 가장 작은 수부터 N까지 작은 수의 배수를 모두 제거합니다.

n=1000
a = (False,False) + (True)*(n-1)
primes=()

for i in range(2,n+1):
  if a(i):
    primes.append(i)
    for j in range(2*i, n+1, i):
        a(j) = False
print(primes)

#include<stdio.h>
#include<cmath>
using namespace std;


int main(){
	int n = 1000;
	int check(1001) = { false };

	check(0) = check(1) = true;
	for (int i = 2; i < sqrt(1000); i++){
		if (check(i) == false){
			for (int j = i + i; j <= 1000; j += i){
				check(j) = true;
			}
		}
	}

	for (int i = 1; i <= n; i++){
		if (!
check(i)) printf("%d ", i);
	}
	


	return 0;
}

(인용하다)

(하나) 파이썬

(2) C++

Related Posts: