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

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

#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

#include <stdio.h>
#include <conio.h>

int main()
{
    //2~1000사이 소수의 개수
    int nCount=0;
    int check = 0;

    for (int i=2; i <= 1000; i++)
    {
        check = 0;
        for (int j=1; j <= i; j++)
        {
            if (i%j == 0)
                check++;
            if (check >= 3)
                break;
            if (i == j)
                nCount++;
        }
    }
    printf("소수의 개수: %d\n", nCount);
    return 0;
}

#에라테네토스의 체
M=int(input('상한을 입력하세요 : '))

def is_prime(n):
    for i in p:
        if n%i==0:
            return False
    return True

p=[]
count=0
for k in range(2, M+1):
    if is_prime(k)==True:
        p.append(k)
        count+=1
print('%d 이하 소수의 개수는 %d개' %(M, count))

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

def prime_formula():
    prime = []
    total_count=0
    max_num =int( input("소수를 구할 Max 값을 입력하세요:"))
    for n in range (1,max_num+1):
        count = 0
        for m in range(1,n+1):
            if ( n % m == 0):
                count += 1
        if ( count == 2):
            prime.append(n)
            total_count += 1
    return total_count

print(prime_formula())

package day5;

public class Test1 {

/*
 * 2이상 1000이하 자연수의 집합에서 소수의 개수를 구하는 알고리즘을 작성하시오.
 */
public static void main(String[] args){
    int arr[]=new int[999];
    int allCount=0;
    int count=0;
    for(int i=0; i<999; i++){
        count=0;
        arr[i]=i+2;
        for(int j=2; j<=arr[i]; j++){
            if(arr[i]%j==0){
                count++;
            }
        }
        if(count==1){
            allCount++;
        }
    }
    System.out.println(allCount);
}

}

파이썬3.4입니다. 역시 알고리즘을 생각하기엔 무리가 있네요. 범위가 조금만 늘어나도 제 컴퓨터에서는 몇초가 걸리더라구요. 다른 분들 코드를 좀더 공부해야겠네요

def fnc(): #기존
    chk = 0
    for n in range(1, 1001):
        for i in range(1, n + 1):
            if n % i == 0:
                chk += 1
        if chk == 2:
            print(n, end =' ')
        chk = 0

def f(li, i = 2): #그나마 개선함
    print(li[0], end = ' ')
    for n in li:
        if n % i == 0:
            li.remove(n) #나눠지는 수는 제거한다
    if li:
        f(li, li[0]) #재귀함수
    else:
        return

f(list(range(2, 1001)))

에라토스체? 알고리즘을 많이 쓰셨길래, 네이버에서 대강 어떤 내용인지 확인하고, 직접 구현해봤어요. 마구잡이로 했던 fnc()보다는 훨씬 낫지만, 아랫분이 짜신 코드를 가지고 같이 돌려보니, 어마어마한 차이가 나네요^^;;;; 100배는 제것이 늦는거 같습니다. ㅎ

def IsPrimeNumber(n):
    for i in range(2,n//2+1): # no need to range(2,n)
        if n%i==0:
            return False
    return True

counter=0
for n in range(2,1001):
    if IsPrimeNumber(n):counter+=1

print("Prime Number in 2-1000 = %d" % counter)

#Python3
prime = 0
for x in range(2, 1001):
    init = False
    for y in range(2, x):
        if x % y == 0:
            init = False
            break
        init = True
    if init == True:
        prime += 1
print("There are ", prime, " prime numbers between 1 and 1000") #167

#include <stdio.h>
#include <conio.h>

int main()
{
    //2~1000사이 소수의 개수
    int nCount=0;
    int check = 0;

    for (int i=2; i <= 1000; i++)
    {
        check = 0;
        for (int j=1; j <= i; j++)
        {
            if (i%j == 0)
                check++;
            if (check >= 3)
                break;
            if (i == j)
                nCount++;
        }
    }
    printf("소수의 개수: %d\n", nCount);
    return 0;
}

public class Three {
    // 2이상 1000이하 자연수의 집합에서 소수의 개수를 구하는 알고리즘을 작성하시오.
    public static void main(String[] args) {
        int count;
        int allCount = 0;
        for (int i = 2; i <= 1000; i++) { 
            count = 0;
            for (int j = 2; j < i; j++) { // j는 나누는 수
                if (i % j == 0)  // 나머지가 0이란건 소수가 아니라는 것.
                    count++;  //count가 올라갔다는건 소수가 아니라는것.
            }
                if (count == 0)  
                    allCount++;
            }

        System.out.println(allCount);
    }
}

print len([i for i in range(2,1001) if sum(i%d==0 for d in range(2,1001))==1 ])

효율은 다른 분들이 많이 따져주셔서,,, 시간복잡도는 무시하고 숏코딩에만 주안점을 두었습니다.

num=list(range(2,1000))
for i in range(2,1000) :
  for j in range(2,1000):
    if i<=j :
      break
    if i%j == 0 :
      num.remove(i)
      break

print(num)

파이썬 2.7.10

n = 1000
p = [True] * n
for i in xrange(3,int(n**0.5)+1,2):
        if p[i]:
                p[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
print len([2] + [i for i in xrange(3,n,2) if p[i]])

>> 168
>> Elapsed time is 0.000135183334351 seconds.




n = 10000000
p = [True] * n
for i in xrange(3,int(n**0.5)+1,2):
        if p[i]:
                p[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
print len([2] + [i for i in xrange(3,n,2) if p[i]])
>> 664579
>> Elapsed time is 0.620986938477 seconds.

에라토스테네스의체, 2,3,5,7의 배수가 아닌 남는 수의 집합에 의거하여 풀려다가 일단 2,3을 소수 리스트에 올리고 반복적으로 나눌 수 없는 값을 추가해 가면서 코딩했습니다.답은 166개인데 맞나요 ㅎㅎ ```{.java}

ArrayList primeNumbers = new ArrayList();

public PrimeNumber(){

    primeNumbers.add(2) ;
    primeNumbers.add(3);
}

public boolean isPrimeNumber(int num){
    int prime = 0 ;
    for(int i = 0 ;i < primeNumbers.size() ; i++){
        prime = (int)primeNumbers.get(i);
        if(num % prime == 0){
            return false;
        }

    }
    return true;
}

public int countPrimeNumber(int n, int m){
    int count = 0 ;
    for(int i = n ;i <= m ;i++){
        if(isPrimeNumber(i)) {
            primeNumbers.add(i);
            count++;
        }
    }
    System.out.println(count);
    return count;
}

```

a=0
i=j=1
sosu=list()
while i<=1000:
    while j<=i:
        if i%j==0:
            a=a+1            
        j=j+1
    if a==2:
        sosu.append(i)
    i=i+1
    j=1
    a=0
print(len(sosu))

자바로 작성

        int count=0;
        loop: 
        for(int i=2;i<1001;i++){
            for(int j=2;j<=i/2;j++)
                if(i%j==0) continue loop;// 소수가 아니면 다음수로
            count++;
        }
        System.out.println("2~1000사이의 자연수의 집합에서 소수의 개수 :" + count + "개");

prime = []
count = 0
for i in range(2,1001):
    hit = 0
    for j in range(1,i): 
        if (i%j == 0):
            hit = hit + 1
    if (hit < 2):
        prime.append(i)
        count = count+1

prime
count

def nprime(n):
    L=[1]*(n+1)
    for i in range(2,n+1):
        if L[i] == 0: continue
        p = i*2
        while p < n+1:
            L[p] = 0
            p += i
    return L.count(1)-2

print nprime(1000)

Perl과 정규표현식을 이용한 방법입니다.

#!/usr/bin/env perl

my $count = 0;
foreach (2..1000) {
    if((1x$_)!~/^1?$|^(11+?)\1+$/) {
        $count++;   
    }
}
print $count;

d=0
c=0
d=1 #2는 따로샌다

for a in range(2,1001):
    for b in range(2,a):
        if a>b and a%b==0:
            c=c+1
        if b==a-1 and c==0:
            d=d+1
        if b==a-1:
            c=0

print(d)

파이썬 3.5.1 입니다. 처음으로 레벨 2 문제 풀어보네요

    public static void main(String[] args) {
        int prime = 0;
        for(int i=2;i<=1000;i++) {
            int count = 0;
            for(int j=1;j<=i;j++) {
                if(i%j == 0) count++;
            }
            if(count == 2) prime++;
        }
        System.out.println(prime);
    }

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)

Java8

CopyOnWriteArrayList<Integer> primeNumber = Lists.newCopyOnWriteArrayList();
        for (int i = start; i < end; i++) primeNumber.add(i);
        primeNumber.removeIf(p -> primeNumber.stream().anyMatch(i -> (p != i) && (p / i >= 1) && (p % i == 0)));
        logger.debug("{}", primeNumber.size());

public class 소수구하기 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        long st = System.currentTimeMillis();

        int num = 1000;
        int not_prime = 0;
        int numOfPrime;

        int 제곱근값 = (int)(Math.sqrt((double)num));

        for(int i=2; i<=num; i++){
            for(int j=2; j<=제곱근값; j++){
                if(i%j == 0 && i!=j) {
                    not_prime++;
                    break;
                }
            }
        }

        numOfPrime = num - not_prime - 1;
        System.out.println("소수의 개수 : " + numOfPrime);
        System.out.println(System.currentTimeMillis() - st + "밀리세컨드");
    }
}

자바로 작성해 보았습니다 숫자가 커짐에 따라 시간복잡도가 제곱배만큼 커지네요 ㅠㅠ
소수가 아님을 판별 하려면 약수 하나만 찾으면 된다는 것에 착안 했습니다
소수가 아닐땐 빨리 검출해낼 수 있는데 소수일 때엔 처음부터 끝까지 제곱근수만큼 검사해야 하기 떄문에 속도가 안나는거 같습니다

#파이썬3.5.1
#한 수의 약수를 구하는 방법은 그 수의 양의 제곱근까지 2부터 모조리 나눈 후 그때 나누어지지 않는 카운트를 세어 나눈 수의 개수와 똑같으면 소수로 판정합니다.
import time, math

print("Start <= ? < Stop")
startnum = int(input("Start : "))
if startnum <= 1:
    startnum = 2
stopnum = int(input("Stop  : "))
print("I will print the prime number(s) in {}<= <{}. Start in 3...".format(startnum, stopnum))
time.sleep(3)
a = 1
b = 0
lis = []

def isprime(p):
    global lis
    b = 0
    for j in lis:
        if p % j != 0 or p == j:
            b += 1
    if b == len(lis):
        return True

for i in range(2, int(math.sqrt(stopnum)) + 1):
    lis.append(i)
for i in range(startnum, stopnum):
    if isprime(i):
        if b == 9:
            b = 0
            print("| {} : {} |".format(a, i))
        else:
            print("| {} : {} ".format(a, i),end=' ')
            b += 1
        a += 1
print("|")

tmp3 = 2
for(i in 3:1000){
  tmp1 = i
  tmp2 = c(2:(i-1))

  if(sum(which(tmp1 %% tmp2 == 0)) == 0) tmp3 = c(tmp3, tmp1)
}
length(tmp3)

R로 작성했습니다. 감사합니다.

count = 0
for i in range(2, 1001):
    chk = 1
    for j in range(2, i):
        if i % j == 0: chk = 0
    if chk: count += 1
print(count)

Python 3.4.4

result = []
candidates = [i for i in range(3, 1000)]
index = 2
product = index

while candidates:
    while product < 1000:
        if product in candidates:
            candidates.remove(product)
        product += index

    result.append(index)
    index = candidates[0]
    product = index
    del candidates[0]

result.append(index)

print(len(result))

numbers = [True] * 1001
numbers[0] = False
numbers[1] = False
for i in range(2,1000):
    for j in range(2,500):
        if (i*j)<1001:
            numbers[i * j] = False
num=0
for i in numbers:
    if i:
        num += 1
print(num)

에라스토스테네스의 체입니다. C++로 제 방식대로 구현해봤어요. 정답인 168을 출력합니다. 시간복잡도가 아마 O(sqrt(n)loglog(n))일듯...

#include <cstdio> 
#include <cstdlib> 
#include <algorithm>
using namespace std;

int notPrime[1001];  

void sieve(){
    notPrime[0] = notPrime[1] = 1;  
    for (int i = 2; i*i <= 1000; i++){
        if (!notPrime[i]){
            for (int j = i*i; j <= 1000; j += i){
                notPrime[j] = 1;  
            }
        }
    }
} 

int main(){
    int cnt = 0; 
    sieve();  
    for (int i = 0; i <= 1000; i++){
        if (!notPrime[i]) ++cnt;  
    }
    printf("%d\n",cnt); 
    return 0; 
}

C#으로 작성했습니다.

public int CountPrimeNumber(int n)
{
var count = 0;
for (int i = 3; i <= n; i+=2)
{
var isPrimeNumber = true;
for (int j = 3; j < i; j+=2)
{
if (i%j == 0)
{
isPrimeNumber = false;
break;
}
}
if (isPrimeNumber) count++;
}
return count;
}

include

int main(void) {
    int i, j;
    int num;
printf(" 정수 입력해 주세요. \n");
scanf("%d",&num);

    for(i = 2; i <= num; i++) {
        for(j = 2; j <= i-1; j++) {
            if(i % j == 0) {
                break;
            }
        }
        if(i == j) {
            printf("%d ", i);
        }
    }

    return 0;
}

public class question1 {
    public static void main(String[] args) {
        int[] number = new int[999];
        int swich = 1;  //첫번째는 놔둬야함
        int count = 0; //소수  개수
        int result;
        for (int i = 2; i < 1001; i++) {
            number[i-2] = i;
        }
        for (int i = 2; i < 1001; i++) {
            result = i;
            while (result < 1001) {
                if (swich == 1){
                    swich = 0;
                }else {
                    number[result-2] = 0;
                }
                result += i;
            }
            swich = 1;
        }
        for (int i = 0; i < 999; i++) {
            if (number[i] != 0) {
                count++;
            }
        }
        System.out.println("소수는" + count+"개");
    }

}

자바로 풀었습니다.

import time

def d_prime(a):
    count=0
    for k in prime:
        if n%k==0:
            while count==0:
                count+=1
    if count==0:
        return True

print("<소수생성기>")
M=int(input("상한을 입력하세요 : "))

n=2
p=0
prime=[]

t1=time.time()
while n<=M: 
    if bool(d_prime(n))==True:
        print(n)
        p=n
        prime.append(n)    
    n+=1
t2=time.time()

print("1부터 %d까지 소수의 개수는 %d개" %(M, len(prime)))
print('%0.2f초 걸렸습니다.' %(t2-t1))

numberlist = []
for i in range(2, 1001):
    numberlist.append(i)

for i in range(2, 40):
        for j in range(2, int(1000/i)+1):
                if i*j in numberlist:
                        numberlist.remove(i*j)

n = 0
while not numberlist == []:
        numberlist.remove(numberlist[0])
        n += 1

print(n)

def prime_numbers(n):
    if n < 2:
        return []
    result = set()
    range_ = set(range(2, n + 1))
    while range_:
        base = min(range_)
        if base ** 2 > n:
            result |= range_
            break
        range_ -= set(range(base, n + 1, base))        
        result |= {base}
    return result

print(len(prime_numbers(1000)))

Python 3.5.2에서 작성하였습니다.

public class CoutnPrime {

    public static void main(String[] args) {
       int num= 0;
       boolean flag = false;
       for (int i =2; i < 1000; i++){
           int subCnt = 0;
           for(int j = 1; j<=i;j++){
               if(i%j == 0){
                   subCnt++;
               }
               if(subCnt >2){
                   break;
               }
           }
           if(subCnt == 2) num++;
       }
       System.out.println(num);
    }

}

#python 2.7.xx
num = 10000
prime_number  =  [ div for div in range(3,num+1,2) if not num % div == 0 ]
print [1,2] + prime_number

한줄로 짜보았습니다

def chk_sosu(num):
    for x in range(2,num):
        if num % x == 0:
            return False
    return True

print(len([x for x in range(2,1001) if chk_sosu(x)]))

#### 2017.01.05 D-413 ####

난 무엇을 기준으로 풀었는가...

sum(1 for n in range(2, 1001) if sum(1 for i in range(2,n) if n%i==0)==0   )

import java.util.ArrayList;
import java.util.Date;
import java.util.List;

public class FindPrimeNumber {

    public static void main(String[] args) {
        Long start = new Date().getTime();
        System.out.println(find2(2, 50000));
        System.out.println(new Date().getTime() - start);
    }

    public static int find2(Integer s, Integer e) {
        List<Integer> prime = new ArrayList();
        prime.add(2);
        for (int i = s; i <= e; i++) {
            for (int j = 0; j < prime.size(); j++) {
                if (i % prime.get(j) == 0) break;
                if (j == prime.size() - 1) prime.add(i);
            }
        }
        return prime.size();
    }
}

public class Test3 {
    // 2이상 1000이하 자연수의 집합에서 소수의 개수를 구하는 알고리즘을 작성
    public static void main(String[] args) {
        int cnt = 0;
        for (int i = 2; i <= 1000; i++) {
            int flag = 0;
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    flag = 1;
                    break;
                }
            }

            if (flag == 0) {
                cnt += 1;
            }
        }
        System.out.println(cnt);
    }

}

class Coding_dj { public static void main(String[] args) { //2이상 1000이하 자연수의 집합에서 소수의 개수를 구하는 알고리즘을 작성하시오. int nocnt; int cnt = 0; for(int i=2 ; i<=1000 ; i++) { nocnt =0; for (int j=2 ;j<i ;j++ ) { if (i % j == 0) { nocnt ++; } } if (nocnt == 0) { cnt++; } } System.out.println(cnt);

}

}

Python 3.6

count = 0

for n in range(2,1001):
    find_factor = list((i, n//i) for i in range(1, int(n**0.5)+1) if n%i == 0)
    if len(find_factor) == 1:
        count += 1

>>> count
168

nat = list(range(2, 1001))
prime = []
while nat:
    n = nat.pop(0)
    prime.append(n)
    nat = [x for x in nat if x % n > 0]

print(len(prime)) #168

Python 3으로 풀었습니다.

def prime_count(n):
    nums = [x for x in range(2, n + 1)]
    for i in range(2, int(n / 2) + 1):
        if i in nums:
            nums = [x for x in nums if x == i or x % i != 0]
    return len(nums)

파이썬에서 is로 하면 객체 비교를 하는 것인지,

일정한 값 이상에서는 동일한 값도 False로 리턴되네요.

Java 처럼 내부적으로 일정한 범위의 값은 cache하는 것 같습니다.

무슨 차이일까 싶었는데, 문제 덕분에 하나 알아갑니다.

nums = [x for x in nums if x is i or x % i is not 0]

#104.(2) 소수의 갯수 구하기

list1 = [x for x in range(2,1001)]

set1 = set(list1)
result = []

while len(list1) != 0:
    prime = list1.pop(0) #제일처음껀 항상 소수
    result.append(prime) #그 값을 result에 넣고
    mul = 1000//prime #기준이 1000이니까 2~1000까지 배수들 뺄 기준을 생각
    hub=[i*prime for i in range(1,mul+1)]
    set1 = set1 - set(hub) #전체셋에 소수의 배수들 빼주고
    list1 = list(set1) #다시 list1생성

result.sort()
print(result)

def f(num1):
    tot1 = [1] * num1
    for i1 in range(2, num1):
        if tot1[i1]:
            tot1[i1*2::i1] = [0]*len(tot1[i1*2::i1])
    print(len([x for x in tot1 if x])-2)

f(10000000)

# python 3.6
lst = [i for i in range(2, 1001)]

pnum = list()
while lst:
    pnum.append(min(lst))
    lst = [v for v in lst if v % min(lst) != 0]
print(len(pnum))
# ans: 168

자바 기본 연산자로만 구현해봤습니다.

이 문제는 코딩 자체는 아주 쉬운것 같은데, 문제는 얼마나 계산을 효율적으로 하는가에 있는 것 같네요. 숫자를 카운트하는데 걸리는 시간까지 계산해보진 않았는데, 제가 작성한 코드는 확실히 비효율적입니다. 그냥 기본 연산자로 초보자가 구현해내는 수준의 코드네요..ㅠㅠ

package ExampleMatterTest;

public class PrimeNumberCount {
    public static void main(String[] args) {
        boolean dividable = false; int count = 1;

        for(int allNum = 3; allNum <= 1000; allNum++) {
            for(int checkingNum = 2; checkingNum < allNum; checkingNum++) {
                if(allNum % checkingNum == 0) {
                    dividable = true;
                }
            }
            if(dividable == false) {
                count++;
            } else {
                dividable = false;
            }
        }
        System.out.println("Result : " +count);
    }
}

public class primeNum {
    public static void main(String[] args) {
        long st = System.currentTimeMillis();
        System.out.println(get_PrimeNum(1000));
        System.out.println(System.currentTimeMillis() - st + "밀리세컨드");
    }

    static int get_PrimeNum(int n){
        int cnt=0;
        boolean[] arr =new boolean[n+1];
        for(int i=2; i<=n; i++){
            arr[i] = true;
        }
        for(int i=2; i < Math.sqrt(n+1); i++){
            if(!arr[i]){ //해당수가 소수이면 트루인채로 지나감  
                continue;
            }
            for(int j=i+i; j<n+1; j += i){ //i의 배수 는 모두 false로 
                arr[j]=false;
            }
        }
        for(int i=0; i< n+1; i++){
            if(arr[i]==true) cnt++;
        }

        return cnt;

    }
}

public class PrimaryNumber {
    public static void main(String[] args) {
        int num = 0; 
        for (int i = 2; i <= 5000; i++) {
            int cnt = 0;
            for (int j = 1; j <= i; j++) {
                if(i % j == 0) cnt++;
            }
            if(cnt == 2) num++;
        }
        System.out.println(num);
    }
}

pool = [i for i in range(2, 10000)]
i = 0
while i < len(pool):
    j = 1
    while i+j < len(pool):
        if not pool[i+j] % pool[i]:
            pool.pop(i+j)
        else:
            j += 1
    i += 1

print(len(pool))

public class Number {

    public static void main(String[] args) {
       int num= 0;
       boolean flag = false;
       for (int i =2; i < 1000; i++){
           int subCnt = 0;
           for(int j = 1; j<=i;j++){
               if(i%j == 0){
                   subCnt++;
               }
               if(subCnt >2){
                   break;
               }
           }
           if(subCnt == 2) num++;
       }
       System.out.println(num);
    }

}

n=range(2,1001)
ru=(0 for i in n)
nums=[[0,2],[1,2]]+list(map(list, zip(n,ru)))

for i in n:
    if not nums[i][1]:
        nums[i][1]=1
        nums[i*2::i]=[[0,2]]*(1000//i-1)
else: result=[x for x,y in nums if y==1]

print(len(result))

http://53perc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%86%8C%EC%88%98-%ED%8C%90%EB%B3%84%ED%95%98%EA%B8%B0 내용 참고했습니다.

def is_prime(num) :
    for i in range(2,num) :
        if num % i == 0 :
            return False
    return True

c = 0
for i in range(2,10000) :
    if is_prime(i) :
        c += 1

print( c )

```{.java} import java.util.Scanner; public class findPrimeNumber { public static void main(String[] args) { System.out.println("2이상의 수를 입력하시오"); Scanner a = new Scanner(System.in); int n = a.nextInt(); //2이상 n이하에서 소수의 개수 구하기 int size = n-1; int[] arr = new int[size]; for (int i=0; i<size; i++) { arr[i] = i+2; }

    // 배열 arr[i] 원소를 2부터 나누어봤을 때 나머지가 0이 된다면 count--
    int count = size;
    for(int i=0; i<size; i++) {
        for(int j=2; j<arr[i]; j++) {
            if(arr[i]%j==0) {
                count--;
                break;
            }
        }
    }
    System.out.println(count);
    a.close();
}

} 소수의 개수 count 변수를 증가하는 것이 아닌, 감소하는 방향으로 코드를 작성했습니다. 소수일때를 판별하는것이 아닌 소수가 아닐 때를 고려했습니다.

dict ={}
for i in range(2,1001):
    dict[i] = list(x for x in range(1,i) if i%x==0)
print("소수 개수:", len(list(key for key in dict.keys() if len(dict[key])==1)))

dict ={}
for i in range(2,1001):
    dict[i] = list(x for x in range(1,i) if i%x==0)
print("소수 개수:", len(list(key for key in dict.keys() if len(dict[key])==1)))

x = int(input("숫자를 입력하세요"))
c,r = 3,[]
for s in range(1,x):
       if s%2==1:
              while c<s:
                     if s%c == 0:
                            break
                     else:
                            c += 2
                            continue
              if c == s:
                     r.append(s)
              c = 3
print(len(r)+1)

파이썬 3.6

factor, count = [],0
# primenumber = []
for i in range(2,1001):
    for h in range(1,i+1):
        if i%h == 0: factor.append(h)
    if len(factor) == 2: count += 1
    factor = []
print(count)

• 결과값

168

r로 풀었습니다.

v<-c(2:1000)
for(n in v){
  for(i in 2:(n-1)){
    if(n%%i==0){
      v<-setdiff(v, n)
    }
  }
}
v<-union(2, v)
print(v)

temp=[]
cou=0
for i in range(2,1001):
        for j in range(2,i+1):
            if i%j==0:
                temp.append(j) 
        if len(temp)==1:
            cou=cou+1
        temp=[]
print(cou)   

function _remove_under (k) {
  return k - Math.floor(k);
}

var array_prime = new Array;
var _cal_num = 0;

for (var i = 2; i < 1001; i = i + 1) {
var _judge_set = 1;
  for (var j = 2; j < i; j = j + 1) {
  _judge_set = _judge_set * _remove_under(i/j);
  }
  if (_judge_set != 0) {
    array_prime.push(i);
    _cal_num = _cal_num +1;
  }
};

console.log(array_prime)
console.log(_cal_num)

자바스크립트로 해보았습니다. 그런데 해보긴 했는데 갯수가 110에서 막힙니다. 저기 '1001'부분을 '4001'로 해도 110에서 막힙니다. 이유를 모르겟습니다.

어디가 잘못된걸까요?;;;

def primeset(n):
    l = list()
    for i in range(2,n+1):
        if all([i%j for j in l]):
            l.append(i)
    return l


print(len(primeset(1000)))

candidates=set()
for num in range(2,1001):
    candidates.add(num)

primes=[2,3,5,7,11,13,17,19,23,29,31]
num_set=set()

for num in candidates:
    for prime in primes:
        if num%prime==0:
            num_set.add(num)
            break

print(len(candidates-num_set)+len(primes))

기본적인 에라토스테네스의 체를 메모리 효율적이고 빠른 비트 연산을 이용하여 적어본 버전입니다.

// gcc 5.1.0 tdm64 컴파일러 이용
// gcc count.c -O3 -o count.exe

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

typedef unsigned char byte;
typedef unsigned int uint;
typedef unsigned long long ulong;

typedef struct
{
    uint byteSize;
    byte *bytes;
} Bits;

void construct(Bits *bits, uint byteSize)
{
    bits->byteSize = byteSize;
    // 모든 바이트 값을 0으로 받아옴.
    bits->bytes = (byte *)calloc(byteSize, 1);
}

void release(Bits *bits)
{
    free(bits->bytes);
}

// 에라토스테네스의 체 구현을 위한 unsigned 64비트 정수를
// 이 프로그램에서 정의한 데이터구조가 약속한 인덱스로 바꿔줌.
uint getByteIndex(ulong bitSize)
{
    // 나누기 대신 더 빠른 Bitwise Operation 사용
    return bitSize >> 3;
}

uint getBitIndex(ulong bitSize)
{
    // 제일 끝에 3 digit을 가져옴
    return bitSize & 7;
}

// 바이트와 비트 번호를 받아들이고 그값이 0인지 아닌지 리턴
// 0이면 체에 걸리지 않았음을 의미하니 소수이고 1이면 합성수
byte getBit(const Bits *bits, uint byteIndex, uint bitIndex)
{
    return bits->bytes[byteIndex] & 1 << bitIndex;
}

// 처음에 모두 바이트들 값이 0으로 초기화되었으니
// 실행해서 합성수로 걸리지는 값을 1로 올림.
void setBitTo1(Bits *bits, uint byteIndex, uint bitIndex)
{
    bits->bytes[byteIndex] |= 1 << bitIndex;
}

void main()
{
    printf("Pi(x) Calculator for [x < 2 ** 34].\nx = ");
    ulong target;
    scanf("%llu", &target);

    // 컴퓨터 사양때문에 프로그램 사용 메모리를 2GB로 제한하기위함.
    // 2 * 2^30(기가바이트) * 2^3(1바이트=8비트) = 2^34
    if (target >= (ulong)1 << 34)
        exit(0);

    uint byteSize = target / 8 + 1;
    ulong bitSize = (ulong)byteSize * 8, j;
    ulong limit = bitSize / 2, i;

    time_t start = clock();
    Bits bits;
    construct(&bits, byteSize);
    // 0과 1은 소수 아님
    setBitTo1(&bits, 0, 0);
    setBitTo1(&bits, 0, 1);

    // 전형적인 에라토스테네스 체로 합성수 비트 1로 올리는 과정.
    for (i = 2; i < limit; ++i)
        if (!getBit(&bits, getByteIndex(i), getBitIndex(i)))
            for (j = i * 2; j < bitSize; j += i)
                setBitTo1(&bits, getByteIndex(j), getBitIndex(j));

    uint count = 0;

    // 입력수까지 소수를 셈
    for (i = 0; i <= target; ++i)
        if (!getBit(&bits, getByteIndex(i), getBitIndex(i)))
            ++count;

    release(&bits);
    time_t finish = clock();
    double elapsedTime = (double)(finish - start) / CLOCKS_PER_SEC;

    printf("\n\nPi(%llu) = %u\n", target, count);
    printf("\n\nExecution Time: %.3f sec\n", elapsedTime);
    system("pause");
}

i7-4700 MQ 2.4GHz 노트북으로 실행한 결과, 10,000,000: 0.1 초 100,000,000: 1.8 초 1,000,000,000: 25 초 정도 걸리네요.

a= set(range(2,1000))
for i in range(2,int(math.sqrt(1000))+1):
    a=a- set(i*j for j in range(2,int(1000/i)+1))

len(a)

public class primeNumber{
 public static void main(String[] args){

  int i,j,m=0;

//3부터 1000까지 검사
  for(i=0;i<998;i++){
   int n=0;
   for(j=0;j<i+1;j++){
    if((i+3)%(j+2)==0)
     break;
    else
     n++;
   }
  if(n==(i+1))
   m++;
  }

//2포함 갯수를 제시
 System.out.println(m+1);
 }
}

Python 3

def erasto(n):
    natural = list(range(2, n + 1))
    delnum = []
    for a in natural:
        if a not in delnum:
            for b in natural:
                if b % a == 0 and a != b:
                    delnum.append(b)
    return sorted(list(set(natural) - set(delnum)))
print(len(erasto(1000)))

흔한 반복문으로 에라스토테네스의 체 함수를 만든 뒤 리턴되는 리스트의 길이를 구하는 방식입니다

// 자바입니다
public static void main(String[] args) throws Exception {
        for (int i=2; i<=1000; i++) {
            for (int j=2; i*j<=1000; j++) {
                notPrime[i*j] = true;
            }
        }

        for (int i=2; i<1000; i++) {
            if(!notPrime[i])
                System.out.println(i);
        }
    }

def sosuu(last_number):
    result = []
    lst = list(range(2,last_number+1))
    for number in lst:
        new_lst = list(range(1,number+1))
        count = 0

        for k in new_lst:
            if number % k == 0:
                count += 1
            else:
                pass

        if count == 2:
            result.append(number)

    return len(result)

print(sosuu(1001))

    // TODO Auto-generated method stub
        int i=2;
        int count;
        int all=0;
        while(i<=1000)
        {   count =0;
            //n으로 나누어지는 수
            for(int n=2;n<i;n++)         
            {   
                if(i%n==0)
                    count++;
            }
            if(count==0)
            {
                all++;
            }
            i++;

        }
        System.out.println(all);

Python

n = 1000
prime = [i for i in range(n+1)]
for i in range(2, n+1):
    if prime[i] == 0:
        continue
    for j in range(i, n+1, i):
        if i == j:
            continue
        #print(j)
        prime[j] = 0
for i in range(2, n+1):
    if prime[i] != 0:
        print(i, end=" ")

import java.text.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer>primes=new ArrayList<Integer>();

        for(int i=2;i<=100000;i++) {
            int count=0;

            for(int k=2;k<i;k++) {
                if(i%k==0) {
                    count++;
                }
            }

            if(count==0) {
                primes.add(i);
            }
        }
        System.out.println(primes.size());
    }
}

n = 1000
nlist = {i:1 for i in range(2,n+1)}
for i,k in nlist.items():
    if k == 0: continue
    if i > int(n**0.5)+1: break
    for j in range(i*2,n+1,i): nlist[j] = 0
print(len([i for i,j in nlist.items() if j==1]))

파이썬 3

list1 = list(range(2, 1001))

for i in range(2, 501):
    list1 = [c for c in list1 if c == i or c % i != 0]

print(len(list1))

num = c(2:1000);

for(n in num){
  for(i in 2:(n-1)){
    if(n%%i==0){
      num=setdiff(num,n);
    }
  }
}
num=c(2,num);
sum(num);

R

def isPrime(p):
    temp=math.factorial(p-1)
    temp=temp%p
    if temp==p-1:
        return(True)
    else:
        return(False)


def howMany(p):
    temp=-1
    k=1
    while k<=p:
        if isPrime(k)==True:
            temp=temp+1
            k=k+1
        else:
            k=k+1
    return(temp)

Python

public static void main(String[] args) {
        int size = 10000000;
        int[] num = new int[size];
        for (int i = 0; i < num.length; i++)
            num[i] = i + 2;
        System.out.println(PrimeNumber(num));
    }

    private static int PrimeNumber(int[] num) {
        for (int i = 0; i < num.length; i++) {
            for (int j = i + 1; j < num.length; j++)
                if (num[i] == 0)
                    break;
                else if (num[j] != 0 && num[j] % num[i] == 0)
                    num[j] = 0;
            if (Math.pow(num[i], 2) > num.length)
                break;
        }
        int sum = 0;
        for (int i = 0; i < num.length; i++)
            sum += num[i] != 0 ? 1 : 0;
        return sum;
    }

prime = [2]

def sieve(k, n):  # k가 소수인지를 판단하고 +1. k는 n까지를 탐색한다. n은 3이상이여야 한다.
    while k <= n:
        for i in prime:
            if k%i == 0:
                break
            else:
                prime.append(k)
                break
        k = k+1
        return sieve(k, n)  # 비교연산까지 수행하기 때문에 선행 증가 필요.
    return prime

print(sieve(2, 100))

저는 python을 사용하였습니다. 재귀함수 연습차 코드를 짜보았는데 maximum이 걸리나봐요ㅜㅜ 혹시 해결방법 아시는 분 있으면 댓글 부탁드려요~~

    class Program
    {
        static void Main(string[] args)
        {
            int nCnt = 0;
            int nNnumber = int.Parse(Console.ReadLine());

            for (int i = 1; i <= nNnumber; i++)
            {
                if (IsMinority(i))
                {
                    nCnt++;
                }
            }
            Console.WriteLine(string.Format("소수의 개수 : {0}", nCnt));
        }

        static bool IsMinority(int n)
        {
            int nDivisor = n / 2;   //약수가 없는 수가 소수이므로 2부터 n/2(자기자신/2)까지만 확인하면 됨
            if (n <= 1)
                return false;

            for (int i = 2; i <= nDivisor; i++)
            {
                if ((n % i) == 0) //n을 i로 나누었을때 나머지가 0이면(즉, i는 n의 약수가 아님)
                {
                    return false; //소수가 아니므로 0반환(i가 약수이므로 n은 소수가 아님)
                }
            }
            return true;
        }
    }

public class KimSanghyeop
{
    public static void main(String[] args)
    {
        int f1,f2;
        int cnt=0;
        for(f1=2;f1<=1000;f1++)
        {
            cnt++;
            for(f2=2;f2<f1;f2++)
            {
                if(f1 %f2 ==0)
                {
                    cnt--;
                    break;
                }
            }
        }
        System.out.println(cnt);
    }
}

def find_sosu(n):
    decision = 1
    for j in range(2,n):
        if n%j == 0:
            decision = 0 
            break                     
    return decision

sosu = []

for i in range(2,1000):
    if find_sosu(i) == 1:
        sosu.append(i)

print(len(sosu))

a <- p <- c(1:1000)

for (i in 2:1000){
  p <- setdiff(p, a[a %% i == 0 & a %/% i != 1])
}
p <- p[-1]

# File : prime.py

def fac(n):
    return [x for x in range(1, n) if n%x==0]


pnum = [x for x in range(2, 1001) if max(fac(x))==1]

print (len(pnum))

def Sosu(max_num):
    res=0
    for i in range(2,max_num): 
        for j in range(2,i+1):
            if i%j==0 and i!=j:
                temp=0
                break
            else:
                temp=1
        res+=temp

    return res

print(Sosu(1000))

def prime_number(n):
    count = 0
    number = []

    for i in range(2, n + 1):
        number.append(i)
#2~n 까지의 수를 number에 저장

    for i in range(2, n + 1):
        if i == -1:
            continue
        elif i*2 > n:
            continue
        else:
            for j in range(i*2, n + 1, i):
                number[j - 2] = -1

#자기 자신을 제외한 나머지 배수들을 -1로 지정

    for i in range(2, n + 1):
        if number[i - 2] != -1:
            count += 1
#-1을 제외하고 세기
    return count

print(prime_number(10000000))

#소수의 개수(m 부터 n 까지)
m=int(input('수 입력(최소): '))
n=int(input("수 입력(최대): "))

co=0
for i in range(m,n+1):
    count=0
    for j in range(2,i):
        if i%j==0:
            count+=1
    if count==0:
        co+=1

print(m,"부터 ",n,"까지의 소수의 개수: ",co,"개")
#m=2,n=1000 => 168개

        static void Main(string[] args)
        {
            Console.WriteLine("*** 코딩도장 Q104 ***");

            int startNum = 2;
            int endNum = 1000;
            int countSosu = 0;
            int countYaksu = 0;

            for (int i = startNum; i < endNum+1; i++)
            {
                countYaksu = 0;
                for (int j = startNum; j < i+1; j++)
                {
                    if (i%j==0)
                    {
                        countYaksu += 1;
                    }
                }

                if (countYaksu==1)
                {
                    Console.WriteLine("{0} 은/는 소수입니다.", i);
                    countSosu += 1;
                }

            }

            Console.WriteLine(startNum + " 부터 " + endNum + " 까지 소수는 " + countSosu + " 개 입니다.");
        }

soSuList = []
for i in list(range(2, 1000 + 1)) :
    soSu = True
    for j in list(range(2, i)) :
        if i % j == 0 :
            soSu = False
            break
    if soSu :
        soSuList.append(i)
print(len(soSuList))

namespace codingdojang__
{
    class Program
    {
        static void Main(string[] args)
        {
            Eratosthenes(1000);
        }
        static void Eratosthenes(int input)
        {
            List<int> temp = new List<int> { };
            for (int i = 2; i <= input; i++)
            {
                for (int e = 2; e < input; e++)
                {
                    if (i != e && i % e == 0)
                    {
                        goto Exit;
                    }
                }
                temp.Add(i);
                Exit:
                    continue;
            }
            foreach (var i in temp)
            {
                Console.Write(i + ", ");
            }
            Console.WriteLine();
        }
    }
}

비쥬얼 스튜디오 2017로 코드를 간결하게 표현해봤어요.

#include <stdio.h>

void main() {

    int cnt = 0;

    for (int i = 2; i <= 1000; i++)
    {
        int sum = 0;
        for (int j = 1; j <= i; j++)
        {
            if (i % j == 0)
            {
                sum++;
            }
        }
        if (sum == 2)
            cnt++;
    }

    printf("2에서 1000까지의 소수의 갯수 : %d", cnt);
}

# n보다 작은 소수 찾기

def find_prime(n):
    # 0 ~ n의 소수를 판별함
    prime_list = [True] * (n+1)
    sqrt_n = int(n ** 0.5)
    prime_list[0] = False
    prime_list[1] = False

    for i in range(2, sqrt_n+1):
        if prime_list[i] == False:
            continue

        for j in range(i*i, n+1, i):
            prime_list[j] = False


    num_prime_list = []
    for i in range(n+1):
        if prime_list[i] == True:
            num_prime_list.append(i)
    return num_prime_list

len(find_prime(1000))
-> 168

에라 토스~ 테네스~ 체

#include <iostream>
#include <time.h>
#include <cmath>
using namespace std;

int eratos[10000001];

int main()
{
    clock_t begin, end;
    int N;
    int sqrtn;
    int cnt = 0;
    begin = clock();

    scanf("%d", &N);
    sqrtn = sqrt(N);

    eratos[0] = -1; eratos[1] = -1;
    for(int i = 2 ; i <= N; i++)
    {
        eratos[i] = i;
    }


    for(int i = 2; i <= sqrtn; i++)
    {
        if(eratos[i] == i)
        {
            for(int j = i * i; j <= N ; j+= i)
            {
                if(eratos[j] == j)
                eratos[j] = i;
            }
        }

    }

    for(int i = 2 ; i <= N; i++)
        if(eratos[i] == i)
            cnt++;

    cout << cnt << endl;
    end = clock();

    cout << double(end - begin) / CLOCKS_PER_SEC << "ms"<< endl;
    return 0;
}

def sosu(LIST,ANS):
    if LIST==[]:
        #print(ANS)
        return len(ANS)

    ANS.append(LIST[0])
    for i in range(1,int(1000/ANS[-1])+1):

        if i*ANS[-1] not in LIST:
            continue
        else:
            LIST.remove(i*ANS[-1])

    return sosu(LIST,ANS)

list0=[i for i in range(3,1001,2)]
print(sosu(list0,[2]))

2부터 1001까지의 작은 스케일이라서 망정이지, 만약 99999999999까지의 스케일이었다면 어떻게 쉽게 접근 할 수 있을까...하여 많이 고민했읍니다. 문제힌트의 거름망을 활용하기 위해서는 일단 99999999999까지의 숫자를 반드시 1회이상은 세어야 한다는 치명적인 단점이 있더군요. 어떻게할까 어떻게 할까 고민고민하다가 결국 오늘은 이렇게 물러서지만... 꼭..구현 할 수있었으면 좋겠읍니다. 이 문제는 얼핏보면, 그냥 단순하게 보일지 몰라도, 진면목은 범위가 천문학적으로 커졌을 떄에도 대응 할 수있도록 하는 코드...인것 같읍니다.

maxi=1000
primes=list(range(2,maxi+1))
d=2
while d<int(maxi**1/2)+2:
    for i in primes:
        if i!=d and i%d==0:
            primes.remove(i)
    d+=1

print(len(primes))

#include <stdio.h>
#include <math.h>

int isPrimenumber(int integer);

void main(){

    int index;
    int numPrime=0;

    for(index=2;index<=1000;index++){
        numPrime = numPrime + isPrimenumber(index);
    }
    printf("%d",numPrime);
}

int isPrimenumber(int integer){

    int starter;

    for(starter=2;(double)starter<=sqrt(integer);starter++){
        if(integer % starter == 0){
            return 0;
        }
    }
    return 1;
}

py

def prime(num):
    list = []
    for n in range(2, num+1):
        count = 0
        for i in range(2, n):
            if n % i == 0:
                count = 1
                break
        if count == 0:
            list.append(n)
    return len(list)

print(prime(1000))

num = 10000
prime_number  =  [ div for div in range(3,num+1,2) if not num % div == 0 ]
print [1,2] + prime_number

def is_prime(n):
    t = 2
    while 1:
        if n>t:
            if n % t ==0:
                return False        
            elif n % t !=0:
                t+=1
        elif t== n:
            return True
counter = 0
for i in range(2,1001):
    is_prime(i)
    if is_prime(i)==True:
        counter+=1
print(counter)

prime = [2]
n = 3

while(True) :
    while n < 1000 :
        primeChk = True
        for i in range(2, n) :
            if n % i == 0 :
                primeChk = False
                break
        if primeChk == True :
            prime.append(n)
        n += 1
    if n == 1000 :
        break
print(prime)
print(len(prime))

파이썬입니다. 먼저 숫자가 소수인지 판별하는 함수를 먼저 만들고 그 밑에 에라토스테네스의 체를 함수로 만들어 봤습니다. 소수의 개수와 그 목록을 출력하게 만들었습니다.

import math

def IsPrime(x):
    for i in range(2, int(math.sqrt(x)+1)):
        if x % i == 0:
            return False
    else: return True


def sieve(N):
    sieve = [True] * N
    for i in range(2, int(math.sqrt(N)+1)):
        if IsPrime(i):
            for j in range(i*2, N, i):
                sieve[j] = False
    a = [x for x in range(2, N) if sieve[x] == True]
    return [len(a), a]

import java.util.Scanner;

public class sol104 {

public static int sosu(int num) {

    for(int i=2; i<= num/2; i++) {
        if(num%i == 0) return 0;
    }

    return 1;
}

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

    int count = 0;

    for(int i=2; i<=1000; i++) {
        count += sosu(i);
    }

    System.out.println(count);

}

}

Python 3.7

num = int(input())
anum = [0, 0] + [1] * (num - 1)
for i in range(2, int(num**0.5) + 1):
    if anum[i]:
        anum[i*i::i] = [0] * ((num - i*(i - 1))//i)
print(len([i for i, a in enumerate(anum) if a]))

num=list(range(2,1001))
count=len(num)
no=0
for i in num:
    a=list(range(2,i))
    for j in a:
        if i%j==0:
            no +=1
            break
print(count-no)

package d104_numbers_prime;
import java.util.Scanner;
public class NumbersOfPrime {

    boolean prime(int in) { //소수인지 체크하는 함수
        boolean out=true;
        for(int i=2; i<in; i++) {
            if(in%i==0) {
                out=false;
                break;
            }
        }
        return out;
    }

    public static void main(String[] args) {
        NumbersOfPrime np = new NumbersOfPrime();
        Scanner sc = new Scanner(System.in);
        int X=sc.nextInt();
        int Y=sc.nextInt();
        int output = 0;

        for(int i=X; i<Y; i++) if(np.prime(i)) output ++;

        System.out.println(output);
    }

}

count = 999
for i in range(2, 1001) :
    for k in range(2, i) :
        if i%k == 0 :
            count -= 1
            break
print(count)

결과

168

list =[]
x=[]
count=0
for i in range(2,1000+1):
    for j in range (2, i+1):
        if  i % j == 0:
            list.append(j)
    if len(list) ==1 :
         count = count+1
         x.append(list)
    list = []   

print (count,x)

public class 소수의개수구해보기 {

    public static void main(String[] args) {

        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i=1; i<1001; i++) {
            list.add(i);
        }
        for(int i=2; i<1000; i++) { 
            for(int j=0;; j++) {
                if(list.size()<=j) {
                    break;
                }
                if(list.get(j)>i) {
                    if(list.get(j)%i==0) {
                        list.remove(j);
                    }
                }
            }
        }
        list.remove(0);
        System.out.println(list);
    }
}

저같은 경우는 1~1000사이의 숫자중 i를 제외한 i의 배수를 제거하는 식으로 하였습니다. 168개 나왔습니다.

list1=[]
for i in range(2,1001):
    div=1
    cnt=0
    while div < 1001:
        if i %div==0:
            cnt += 1
        div += 1
    if cnt==2:
        list1.append(i)
print(len(list1))

n=int(input("2보다 큰 정수 n을 입력하십시오: ")) #1000
c=n-1
for num in range(2,n+1):
    for k in range(2,int(num**(1/2))+1):
        if num%k==0 :
            c-=1
            break
print(c) #168

100만까지는 무리없이 잘 계산되네요. 1000만부터는 확실히 느려집니다.

파이썬 3입니다.

N = 1000

prime_list = []

for n in range(3,N+1,2):
    is_prime = True
    for p in prime_list:
        if p > N**(0.5): break
        if n%p == 0:
            is_prime = False
            break
    if is_prime == True: prime_list.append(n)

print(len(prime_list)+1)

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

    if temp_cnt == 1:
        count += 1

print(count)

n=0
for i in range (2,1001):
j=1
while(j<i):
j=j+1
if i%j==0:
if i==j:
n=n+1
break
print(n)

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

//168개
int main() {
    int count;
    int sosoo = 0;
    for (int i = 2; i <= 1000; i++) {
        count = 0;
        for (int j = 1; j <= i; j++) {
            if (i%j == 0)++count;
        }
        if (count == 2)++sosoo;
    }

    cout << "2부터1000까지 소수의 개수는" << sosoo << endl;
}

def primes_up_to_good(n):
    seive = [False, False] + [True] * (n - 1)
    for k in range(2, int(n ** 0.5 + 1.5)):
        if seive[k]:
            seive[k*2::k] = [False] * ((n - k) // k)
    return [x for x in range(n+1) if seive[x]]

print(len(primes_up_to_good(2000)))

sosu = []
for i in range(2,1001):
    cnt = 0
    for j in range(1,i):
        if i%j == 0:
            cnt += 1
        else:
            continue
    if cnt == 1:
        sosu.append(i)
    else:
        continue
print(len(sosu))

def sosu(b): #1000넣으면 됨 
    count = 0
    for i in range(2,b+1):
        for j in range(2,int(i**(1/2))+1): 
            if (i % j) == 0 : 
                count += 1 
                break
    sosu = (b-1) - count  
    return sosu

첫번째 루프(i) : 1000까지 모든 숫자

두번째 루프(j) : 2~sqrt(i)+1 까지 돌림; '소수는 나머지 0인게 없다'를 역으로 생각

if 나머지 0인게 있으면 소수 아님,

break 걸어서 두번째 루프를 나갑니다(count 개수만 올려주고여). 2~1000사이 전체 개수에서 count개수 빼주면 소수 개수입니다.

시간은 Wall time: 997 µs 나오네요!!

%time sosu(1000)

def sieve(n):
    L1=[]
    L2=[i for i in range(2,n)]
    S=set()
    for i in range(2,n):
        for j in range(2,i):
            L1.append((i,j,i%j))
    for p in L1:
        if p[2]==0:
            S.add(p[0])
    S=list(S)
    for q in S:
        L2.remove(q)
    print(len(L2))

sieve(1000)

public class Test1 {
    public static void main(String[] args) {
        int n = 2;
        int cnt = 0;
        while(n <= 1000) {
            if(Prime_num(n)) cnt++;
            n++;
        }
        System.out.println(cnt);
    }

    public static boolean Prime_num(int input) {
        for(int i = 2; i < input; i++) {
            if(input % i == 0) return false;
        }
        return true;
    }
}

Pf = int(input('input number whichever:'))
for i in range(2,Pf+1):
    for j in range(1, i+1):
            if i % j == 0:
                a += [j]  
    if len(a) == 2:
        b += [i]
    a = []
print(b)

count = 0
for i in range(2,1001):
    result = []
    for k in range(1, i + 1):
        if i % k == 0:
            result.append(k)
    if len(result) == 2:
        count += 1
print(count)

def check(N):
    check = 0
    for i in range(1,N):
        if N % i == 0:
            check +=1
    if check == 1:
        return 1
    else:
        return 0
count = 0
for i in range(2,1001):
    if check(i) == 1:
        count += 1
print(count)

#include <iostream>

using namespace std;

int countcheck(int N) {
    int check = 0;
    for (int i = 1; i < N; ++i) {
        if (N % i == 0) {
            ++check;
        }
    }
    return check;
}
int main() {
    ios::sync_with_stdio();
    int count = 0;
    for (int i = 2; i <= 1000; ++i) {
        if (countcheck(i) == 1) {
            ++count;
        }
    }
    cout << count << endl;
    return 0;
}

package main

import "fmt"

func countcheck(N int) int {
    var check int = 0
    for i := 1; i < N; i++ {
        if N%i == 0 {
            check++
        }
    }
    return check
}
func main() {
    var count int = 0
    for i := 2; i <= 1000; i++ {
        if countcheck(i) == 1 {
            count++
        }
    }
    fmt.Print(count)
}

using System;

namespace main
{
    class Program
    {
        static int Countcheck(int N)
        {
            int check = 0;
            for(int i = 1;i < N; i++)
            {
                if(N % i == 0)
                {
                    check++;
                }
            }
            return check;
        }
        static void Main(string[] args)
        {
            int count = 0;
            for(int i = 2;i <= 1000; i++)
            {
                if(Countcheck(i) == 1)
                {
                    count++;
                }
            }
            Console.WriteLine(count);
        }
    }
}

package main;

public class main {
    static int countcheck(int N) {
        int check = 0;
        for(int i = 1;i < N;i++) {
            if(N % i == 0) {
                check++;
            }
        }
        return check;
    }
    public static void main(String[] args) {
        int count = 0;
        for(int i = 2;i <= 1000;i++) {
            if(countcheck(i) == 1) {
                count++;
            }
        }
        System.out.println(count);
    }
}

def count_numer():

  for_answer=[2]

  for i in range(3,1001,1):

     check=True

    for j in for_answer:

      if i%j!=0:

        check=False

    if check==True:

      for_answer.append(i)

  return len(for_answer)

print(count_numer())

a = set(range(2,1001))
b = set()
for i in range(3,1001):
    for j in range(2,i):
        if i%j ==0:   
            b.add(i)

print(len(a-b))

def sosu(num):
    indicator = 0
    for i in range(2, int(num)):
        if int(num) % i == 0:
            indicator = 1
    if indicator == 0:
        return True

result = []
for i in range(2,1001):
    if sosu(i):
        result.append(i)

print('Total : {}'.format(len(result)))

mir = 0
for i in range(2,1000):
    l=[]
    for a in range(1,i+1):
        if i%a==0: l.append(i)
    if len(l)==2: mir+=1
print(mir)

public class Code01 {
        public static void main(String[] args) {
            int count = 0;
            for(int n = 2; n<=1000; n++) { // 2부터 1000까지 자연수 
                boolean isPrime = true; // 일단 무조건 소수
                for(int i = 2; i*i<=n; i++) { // 나눠지는 수를 구하는 조건식(제곱근)
                    if(n%i==0) isPrime = false; // 나눠지면 false 
                }

                if(isPrime) // 소수면 
                    count++; // 개수 1씩 증가
            }
      System.out.println(count); // 소수일때 count된 값을 출력 
        }
    }

python 3.9.6입니다.

# 소수의 개수 구해보기

a = list(range(2, 1001))
for num in range(2, int(1000**0.5)+1):
    for number in a:
        if not number % num and number // num >= 2: a.remove(number)
print(len(a))

실행 결과: 168

#codingdojing_primeNum

from math import sqrt

prime = []

for i in range(2,1001):
    flag = True
    for j in range(2, round(sqrt(i)+1)):
        if i%j == 0: 
            flag = False
            break
    if flag:
        prime.append(i)

print(prime)

def decimal(a):
    count = 0
    for i in range(2,a+1):
        cnt = 0
        for  c in range(1,i+1):
            if i%c == 0:
                cnt += 1
        if cnt == 2:
            count += 1

    return count       

if __name__ == '__main__':
    a = int(input())
    print(decimal(a))

var result = 0;
for (i = 2; i<=1000; i++) {
   var count = 0;
   for(j=2; j<i; j++) if(i%j == 0) count++
   if(count == 0 && i!=1) result++        
}
console.log(result)

cnt =0
for i in range(2,1001) :
    n =0
    for k in range(1,i+1):
        if i%k == 0:
            n+=1
    if n==2:
        cnt +=1

print(cnt)

약수의 수가 2개인 애들로 구해봤는데 1000이하의 자연수에서는 제일 간단하지 않을까싶네요

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

list = [ i for i in range(2,1001)]
result =[]

def divide(num):
    for i in range(2,1001):
        if (num % i == 0) and (num>i):
            result.append(list[i])
            break

for i in range(2,1000):
    divide(i)

print(999-len(result))

// Rust

// 1자리(<10) 소수 : 2, 3, 5, 7

// 2자리 이상(>=10) 소수의 끝자리 숫자는 반드시 1, 3, 7, 9입니다 (0, 2, 4, 5, 6, 8은 2나 5로 나누어짐)

// 따라서 2자리 이상 소수는 11부터 2씩 증가시켜(끝자리 5는 제외) 체로 검사하거나,

// 끝자리 5 제외를 위해 모든 루프에서 %5==0 검사하기가 싫어서 아래와 같이 끝자리 1, 3, 7, 9인 경우 같은 같은 코드를 반복

// 단, 이 경우 마지막 소수 몇 개가 limit 값을 넘어갈 수 있어, 마지막에 전체 소수가 limit이하로 검사하는 코드가 있음

// 이 검사가 모든 루프에서 %5==0 을 적용하는 것보다는 빠르다고 생각됩니다.

fn sieve(limit: u128) -> HashSet {

assert!(limit > 10);
let mut set = HashSet::new();
for i in [2, 3, 5, 7] {
    set.insert(i);    
}
let mut n = 9;
while n <= limit {
    n += 2;
    if set.iter().all(|p| n % p !=0) {  // 끝자리 1인 n이 소수인가?
        set.insert(n);
    }        
    n += 2;
    if set.iter().all(|p| n % p !=0) {  // 끝자리 3인 n이 소수인가?
        set.insert(n);
    }
    n += 4;
    if set.iter().all(|p| n % p !=0) {  // 끝자리 7인 n이 소수인가?
        set.insert(n);
    }
    n += 2;
    if set.iter().all(|p| n % p !=0) {  // 끝자리 9인 n이 소수인가?
        set.insert(n);
    }
}
set.retain(|&k| k <= limit);
set

}

[test]

fn test() {

assert_eq!(sieve(1000).len(), 168);

}

def prime(n):
    pnl = prime_number_list = [2]
    for i in range(3,n+1):
        if min([i%x for x in pnl]) != 0: pnl.append(i)
    return len(pnl)

%time prime(100000)

package org.javaturotials.ex;
import java.util.*;


public class test {
    public static void main(String[] args) {
        int num=0;
        for(int i=2; i<=1000; i++) {
            int count =0;
            for(int j=2; j<=i; j++) {
                if(i%j==0) {
                    count++;
                }
            }
            if(count==1) {
                num++;
            }
        }
        System.out.println(num);
    }
    }

numbers=list(range(3,1000,2))

for i in numbers:
    for j in range(2,1000//i+1):
        if i*j in numbers:
            numbers.remove(i*j)
        else:
            pass
print(numbers)
print(len(numbers))

li1=[] for i in range(2,1001): li=[] for j in range(2,i): if i%j==0: li.append(j) if len(li)==0: li1.append(i) print(len(li1))

def prime(n):
    count = n-1
    for i in range(2,n+1):
        for x in range(2,i):
            if i % x == 0:
                count -= 1
                break
    return count

print(prime(1000))

minNum=2
maxNum=1001
count=1
for i in range (minNum,maxNum):
    for j in range(2,i):
        if i%j==0:
            break
        elif j==i-1:
            count+=1            


print(count)