소수의 개수 구해보기.

2이상 1000이하 자연수의 집합에서 소수의 개수를 구하는 알고리즘을 작성하시오.

에라토스테네스의 체

2016/03/01 10:05

lovegalois2

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

60개의 풀이가 있습니다. 1 / 6 Page

에라토스테네스의 체입니다.

def sieve(n):
    if n < 2:
        return []
    s = [0, 0] + [1] * (n - 1)
    for i in range(2, int(n**.5)+1):
        if s[i]:
            s[i*2::i] = [0] * ((n - i)//i)
    return [i for i, v in enumerate(s) if v]

print(len(sieve(1000)))

천만 이하의 소수를 세는데는 약 1.82초 걸리는군요.

In [12]: %time len(sieve(10000000))
Wall time: 1.82 s
정말 빠르네요^^ - 디디, 2016/03/23 15:55 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#coding: CP949
Data = list(range(3,1001,2)) # 3이상 1000이하 홀수의 리스트.
Answer = []
for i in Data:

    if i == 3 or i == 5: # 3,5는 소수이므로 Answer에 넣는다.
        Answer.append(i)

    else: # List에 i를 j(=3,5,7,~~~)를 나눈 나머지를 입력.
        j=3
        List=[]
        while j <=  i/2:
            List.append(i%j)
            j+=2
        if all(List): # List의 나머지가 모두 0이 아니면 소수.
            Answer.append(i)

print(len(Answer)+1) # 소수 2를 포함해야함.

파이썬 3.4
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def primenums(n):
    if n > 100:
        all = set(i for i in range(int(n/10 + 1), n + 1))
        difference = set()
        for i,x in enumerate(primenums(int(n / 10))):
            for j in range(int(n/10 + 1), n + 1):
                if j % x == 0:
                    difference.add(j)
        return (all - difference) | primenums(int(n / 10))
    if n == 100:
        all = set(i for i in range(11, 101))
        difference = set()
        for i, x in enumerate(set([2,3,5,7])):
            for j in range(11, 101):
                if j % x == 0:
                    difference.add(j)
        return (all - difference) | set([2,3,5,7])
    if n == 10:
        return set([2,3,5,7])
print(sorted(primenums(1000)))

재귀함수로 에라토스테네스의 체를 구현해보았습니다.

속도가 느린것이 단점이네요...

10의 배수 단위로만 범위를 정할 수 있지만 return되는 리스트의 범위를 따로 정하면 그 외 다른숫자도 가능할것 같습니다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#include <stdio.h>
#include <iostream>

using namespace std;

int d[1001];

int main()
{
    for (int i = 2; i <= 1000; i++)
    {
        for (int j = i + i; j <= 1000 / 2; j += i)
        {
            d[j] = 1;
        }
    }

    int cnt = 0;
    for (int i = 2; i <= 1000; i++)
    {
        if (d[i] == 0) cnt++;
    }

    printf("cnt:%d\n", cnt);
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Ruby

크리스탈 풀이 추가. (1000만기준 0.092초. 두가지로 품. 에라토스테네스의 체가 빠름.

# Sieve of Eratosthenes 
primes =->n,s=[1]*n{ (2..n).select{|e| (e*2..n).step(e){|i|s[i-1]=0} if s[e-1]>0}.size }
# loop way
primes =->n{ (2..n).select{|e|(2..Math.sqrt(e)).none?{|f|(e%f)==0}}.size }

Crystal

def count_primes(max)
  # Sieve of Eratosthenes
  sieve = Array.new(max + 1, true)
  sieve[0] = sieve[1] = false
  2.step(max**0.5) {|i| (i*i).step(max,i) {|j| sieve[j]=false } if sieve[i] }
  sieve.count {|e|e}
end

Test

expect(primes[1000]).to eq 168
expect(primes[10000000]).to eq 664579
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

C# 입니다. 저도 마찬가지로 에라토스테네스의 체 알고리즘으로 풀어봤습니다.

int n = 1000, nPrime = n - 1;          
bool[] prime = Enumerable.Repeat(true, n + 1).ToArray();            

Stopwatch sw = new Stopwatch();
sw.Start();

for (int i = 2; (i * i) <= n; i++)
{
    if (prime[i] == false) continue;

    for (int j = i * i; j <= n; j += i)
    {
        if (prime[j] == false) continue;

        prime[j] = false;
        nPrime--;
    }
}
sw.Stop();

Console.WriteLine("n : " + n);
Console.WriteLine("nPrime : " + nPrime);
Console.WriteLine("Elapsed Time : " + sw.Elapsed);

결과

n : 1000
nPrime : 168
Elapsed Time : 00:00:00.0000048

n : 10000000
nPrime : 664579
Elapsed Time : 00:00:00.0882254
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

python 3.5

from math import sqrt

def is_prime(num):
    if num > 1:
        for i in range(2, int(sqrt(num))+1):
            if num % i == 0:
                return False
        return True
    else:
        return False

count = 0
for i in range(2, 1001):
    if is_prime(i):
        count += 1

print(count) 


※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

아래 내용을 참고하였습니다. python 3.5 https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

def get_prime_num(limit):

    current = 2
    num_list = [x for x in range(2, limit+1)]
    tmp_list = []

    while current ** 2 <= limit:
        num_list = list(filter(lambda x: x % current, num_list))
        tmp_list.append(current)
        current = num_list[0]

    return tmp_list + num_list


print(len(get_prime_num(1000)))
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

에라토스테네스의 체를 기반으로 문제 풀어 보았습니다.

/*
 * 2이상 1000이하 자연수의 집합에서 소수의 개수를 구하는 알고리즘을 작성 하시오.
 */
#include <stdio.h>
#include <time.h>

#define MIN_NUMBER 2
// #define MAX_NUMBER 1000
#define MAX_NUMBER 10000000

int main()
{
    // 소수가 아닌 값들은 1로 셋팅
    int * isNotPrimeNumber;
    long countPrimeNumber = 0;
    long i, j;

    // 경과 시간 계산을 위한 체크
    clock_t start, end;

    isNotPrimeNumber = (int *) malloc(sizeof(int) * (MAX_NUMBER + 1));
    memset(isNotPrimeNumber, 0, sizeof(int) * (MAX_NUMBER + 1));

    start = clock();
    for (i = MIN_NUMBER; i <= MAX_NUMBER; i++) {
        if (isNotPrimeNumber[i] == 0) {
            for (j = i + i; j <= MAX_NUMBER; j += i) {
                isNotPrimeNumber[j] = 1;
            }
        }
    }

    for (i = MIN_NUMBER; i <= MAX_NUMBER; i++) {
        if (isNotPrimeNumber[i] == 0) {
            countPrimeNumber ++;
        }
    }
    end = clock();

    free(isNotPrimeNumber);

    printf("(%d - %d)prime number count >>> %ld\n", MIN_NUMBER, MAX_NUMBER, countPrimeNumber);
    printf("Elapsed Time >>> %f\n", (double) (end - start) / CLOCKS_PER_SEC);
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
from itertools import count
from time import time
def prime(n):
    li = [2]
    for i in count(3):
        for x in li:
            if i%x == 0:
                break
        else:
            li.append(i)
        if i > n:
            return len(li)
t = time()
print(prime(1000), '\n', time()-t)

n까지의 소수를 계산합니다. 더 좋은 알고리즘은 딱히 떠오르지 않습니다. 파이썬 3.5.1

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

에라토스테네스의 체 x 1

언어별 풀이 현황
전 체 x 60
python x 33
cpp x 4
ruby x 1
cs x 2
기 타 x 6
java x 12
perl x 1
r x 1