백준 1929번 - 소수구하기

 

▶ 소수란 약수가 1과 자기 자신 밖에 없는 수를 말합니다 (약수의 갯수가 2개인 수를 말합니다)

다시 말해서, N이 소수가 되려면 1과 자기자신을 제외한 나머지 수 중에 나누어 떨어지는 수가 있으면 안됩니다

[ 문제 ] 입력 받은 수가 소수이면 'Yes' 소수가 아니면 'No'를 출력하는 프로그램을 작성하시오

- 방법1 : 2부터 N-1까지 수 중 나누어 떨어지는 수가 있으면 소수가 아니다

#include <stdio.h>
int main()
{
	int N, i;
	bool sw=false; 
	scanf("%d", &N);
	
	for(i=2;i<=N-1;i++)
	{
		if(N%i == 0)
		{
			sw = true;
		}
	}
	if(sw)
		printf("No\n");
	else
		printf("Yes\n");
	
	return 0;
}

 

- 방법 2 : N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같기 때문에 for문을 2부터 N/2 까지만 확인해본다.

#include <stdio.h>
int main()
{
	int N, i;
	bool sw=false; 
	scanf("%d", &N);
	
	for(i=2;i<=N/2;i++)
	{
		if(N%i == 0)
		{
			sw = true;
		}
	}
	if(sw)
		printf("No\n");
	else
		printf("Yes\n");
	
	return 0;
}

 

- 방법3 : 루트 N까지만 검사해보면 된다.

#include <stdio.h>
int main()
{
	int N, i;
	bool sw=false; 
	scanf("%d", &N);
	
	for(i=2;i*i<=N;i++)
	{
		if(N%i == 0)
		{
			sw = true;
		}
	}
	if(sw)
		printf("No\n");
	else
		printf("Yes\n");
	
	return 0;
}

 

[ 문제 ] www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

▶ 에라토스테네스의 체란 1부터 N까지 범위 안에 들어가는 모든 소수를 구하는 알고리즘입니다.

방법 : ① 2부터 N까지 모든 수를 써놓는다

        ② 2를 제외한 2의 배수를 모두 지운다

        ③ 3을 제외한 3의 배수를 모두 지운다

        ④ 5를 제외한 5의 배수를 모두 지운다.... 나머지 수들도 같은 방법으로....

        ⑤ 최종적으로 남은 수가 소수입니다. 

 

[ 문제 ]  입력받은 n까지 소수의 갯수를 구하는 문제입니다. (에라토스테네스의 체)

● 프로그래머스 1단계 - 소수 찾기 문제

●www.acmicpc.net/problem/1929

< 소수구하기 문제를 아래 소스를 참고해서 풀어보세요 >

1929번: 소수 구하기

 

 

★ 1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용합니다.

 

#include <iostream>
using namespace std;
bool check[10000001];

int main() 
{
	int N;
    int answer = 0;
   
    cin >> N;
	
    check[0] = check[1] = true;
    
    for (int i=2; i*i<=N; i++) 
    {
        if (check[i] == false) 
        {
            for (int j=i+i; j<=N; j+=i) 
            {
                  check[j] = true;
            }
        }
   }
   for (int i=2; i<=N; i++) 
   {
        if (check[i] == false) 
        {
        	answer ++;                 //소수의 갯수를 구합니다.
        }
    }
    cout << answer;
    return 0;
}