문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하며, 한 줄로 이루어져 있다. (n ≤ 123456)

입력의 마지막에는 0이 주어진다.

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

 

https://kplee.tistory.com/58

 

백준 문제 번호 : 1978 - 소수찾기

문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하��

kplee.tistory.com

해당 알고리즘 응용하여 작성

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using System;
using System.Text;
 
class Program
{
    static void Main(string[] args)
    {
        StringBuilder sResult = new StringBuilder();
        for(;;)
        {
            int n = int.Parse(Console.ReadLine());
            if(n==0) break;
            bool bPrime = true;
            int iCount = 0;
            for(int i = n+1; i <= 2*n; i++)
            {
                bPrime = true;
                int j = 2;
                do
                {
                    if((i==1 || i%j==0)&& i!=j)
                    {
                        bPrime = false;
                        break;
                    }
                    j++;
                }while(j <= Math.Sqrt(i));
                if(bPrime) iCount++;
            }
            sResult.Append(iCount + "\n");
        }
        Console.WriteLine(sResult);
    }
}
 cs

 

https://www.acmicpc.net/problem/4948

 

4948번: 베르트랑 공준

문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 ��

www.acmicpc.net

 

'void Algorithm' 카테고리의 다른 글

백준 문제 번호 : 1085 - 직사각형에서 탈출  (0) 2020.08.05
백준 문제 번호 : 9020 - 골드바흐의 추측  (0) 2020.08.03
백준 문제 번호 : 1929 - 소수 구하기  (0) 2020.07.27
백준 문제 번호 : 2581 - 소수  (0) 2020.07.26
백준 문제 번호 : 1978 - 소수찾기  (0) 2020.07.25

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

두 가지 방법으로 풀어보았다.

 

첫 번째는 

https://kplee.tistory.com/58

 

백준 문제 번호 : 1978 - 소수찾기

문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하��

kplee.tistory.com

여기서 푼 방법을 이용하여 알고리즘을 작성함.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
using System;
using System.Linq;
 
class Program
{
    static void Main(string[] args)
    {
        int[] arrNum = Console.ReadLine().Split().Select(a => int.Parse(a)).ToArray();
        
        bool bSosu = true;
        for(int i = arrNum[0]; i <= arrNum[1]; i++)
        {
            bSosu = true;
            int j = 2;
            do
            {
                if((i==1 || i % j == 0) && i != j)
                {
                    bSosu = false;
                    break;
                }
                j++;
            }
            while(j <= Math.Sqrt(i));
            if(bSosu)
            {
                Console.WriteLine(i);
            }
        }
    }
}
 cs

위의 방법을 사용했을때 메모리와 시간이다.

 

두 번째는 에라토스테네스의 체를 이용한 방식이다.

문제 하단에 알고리즘 분류에 에라토스테네스의 체가 적혀있어서 관련 내용을 찾아보고 그 방식을 이용하여 알고리즘을 작성함.

 

에라토스테네스의 체가 어떤건지는 구글에 검색하면 자세히 나온다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
using System;
using System.Linq;
 
class Program
{
    static void Main(string[] args)
    {
        int[] arrNum = Console.ReadLine().Split().Select(a => int.Parse(a)).ToArray();
        bool[] bSosu = Enumerable.Repeat(true, arrNum[1] + 1).ToArray();
        bSosu[1] = false;
        
        for(int i = 2; i <= Math.Sqrt(arrNum[1]); i++)
        {
            if(bSosu[i])
            {
                for(int j = i*i; j <= arrNum[1]; j += i)
                {
                    bSosu[j] = false;
                }
            }
        }
        
        for(int i = arrNum[0]; i <= arrNum[1]; i++)
        {
            if(bSosu[i])
            {
                Console.WriteLine(i);
            }
        }
    }
}
 cs

두 번째 방법을 사용했을때 사용되는 메모리와 시간이다. bool 배열 때문에 메모리의 사용량은 더 많지만 시간은 더 적게 걸린다.

'void Algorithm' 카테고리의 다른 글

백준 문제 번호 : 9020 - 골드바흐의 추측  (0) 2020.08.03
백준 문제 번호 : 4948 - 베르트랑 공준  (0) 2020.07.29
백준 문제 번호 : 2581 - 소수  (0) 2020.07.26
백준 문제 번호 : 1978 - 소수찾기  (0) 2020.07.25
백준 문제 번호 : 1011 - Fly me to the Alpha Centauri  (0) 2020.07.23

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

 

https://kplee.tistory.com/58?category=685899

 

백준 문제 번호 : 1978 - 소수찾기

문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하��

kplee.tistory.com

해당 문제에서 사용한 소수찾기 알고리즘을 이용하여 작성함

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using System;
using System.Linq;
 
class Program
{
    static void Main(string[] args)
    {
        int M = int.Parse(Console.ReadLine());
        int N = int.Parse(Console.ReadLine());
        
        int iTotal = 0;
        int iMin = 0;
        
        bool bSosu = true;
        for(int i = M; i <= N; i++)
        {
            bSosu = true;
            int j = 2;
            do
            {
                if((i==1 ||i % j == 0) && i != j)
                {
                    bSosu = false;
                }
                j++;
            }
            while(j <= Math.Sqrt(i));
            if(bSosu)
            {
                iTotal += i;
                if(iMin == 0) iMin = i;
            }
        }
        if(iTotal != 0)
        {
            Console.WriteLine(iTotal);
            Console.WriteLine(iMin);
        }
        else 
        {
            Console.WriteLine("-1");
        }
    }
}
 cs

 

https://www.acmicpc.net/problem/2581

 

2581번: 소수

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.  단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

www.acmicpc.net

 

'void Algorithm' 카테고리의 다른 글

백준 문제 번호 : 4948 - 베르트랑 공준  (0) 2020.07.29
백준 문제 번호 : 1929 - 소수 구하기  (0) 2020.07.27
백준 문제 번호 : 1978 - 소수찾기  (0) 2020.07.25
백준 문제 번호 : 1011 - Fly me to the Alpha Centauri  (0) 2020.07.23
백준 문제 번호 : 2775 - 부녀회장이 될테야  (0) 2020.07.21

+ Recent posts

티스토리툴바