소수 풀이

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

백준 기본 수학 2 2단계 - 2581번 소수를 풀어보았다.

 

풀이: 10000까지 소수를 다 구하고, 뒤집어서 문제를 풀었다.

 

C++

#include <iostream>
#include <cmath>

using namespace std;
int main()
{
  int m,n;
  scanf("%d",&m);
  scanf("%d",&n);
  int nums[10001]={0,};
  for(int j=2;j<10001;j++) nums[j]=j;
  for(int k=2;k<10001;k++)  // 에라토스테네스의 체
  {
    if(nums[k]==0) continue;
    for(int l=2*k;l<10001;l+=k) nums[l]=0;
  }
  int sum=0;
  int small=0;
  for(int h=n;h>=m;h--) // 최소의 소수와 소수들의 합을 찾음
  {
    if(nums[h]!=0)
    {
      sum+=nums[h];
      small=nums[h];
    }
  }
  if(sum==0) printf("%d",-1);
  else
  {
    printf("%d\n",sum);
    printf("%d",small);
  }
}

Python

arr=[True]*10000
m=int(10000**0.5)
for i in range(2,m+1):
	if arr[i]==True:
		for j in range(i+i,10000,i):
			arr[j]=False
narr=[i for i in range(2,10000) if arr[i]==True]

narr.reverse() # 최소값을 위해서 뒤집음
m=int(input())
n=int(input())
sum=0
min=100000
for i in narr:
	if i<=n: # m과 n 사이에 있는 소수는 더하기
		if i>=m:
			sum+=i
	if i>=m: min=i # m보다 큰 가장 작은 소수 구하기
if sum==0: print(-1) 
else:
	print(sum)
	print(min)

Java