15번

1번째 방법

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	int resultcnt = 0;
	int cnt = 0;
	int N;
	cin >> N;
	vector<int> arr(N);
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			if (i%j == 0)
			{
				cnt++;
			}
		}
		if (cnt == 2)
		{
			resultcnt++;
		}
		cnt = 0;
	}
	cout << resultcnt;
}

 

위 방법은 각 숫자의 약수를 계산해 약수갯수가 2 이면 소수로 판단하는 프로그램이다

하지만 이방법은 모든 숫자를 1부터 자기 자신의 숫자까지 다 나눗셈을 하기때문에 제한시간이 1초를 초과한다

 

따라서 그냥 약수의 갯수가 2가 넘으면 그냥 소수가 아니라고 바로 판단하고 break를쓰고 다음 숫자로 넘어가도록 구현해보았다.

 

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	int resultcnt = 0;
	int cnt = 0;
	int N;
	int div = 0;
	cin >> N;
	vector<int> arr(N);
	for (int i = 2; i <= N; i++)
	{

		for (int j = 1; j <= i; j++)
		{
			
			if (cnt > 2)//약수갯수가 그냥 2 넘으면 소수가 아니니 바로 break 를써서 시간을 대폭 감소시킴
			{
				break;
			}
			else if(i%j == 0)
			{
				cnt++;
			}
			
		}
		if (cnt == 2)
		{

			resultcnt++;
		}
		cnt = 0;
	}
	cout << resultcnt;
}

하지만 이렇게 해도 제한시간 1초 지남...,,,ㅡㅡ

 

결국 수학적 머리가 있어야 풀 수 있는 문제입니다...

소수는 숫자의 제곱근 이하의 숫자만 나눠서 약수를 확인해보면 됩니다 그 이후의 숫자는 굳이 안해도됩니다.

 

예를 들면 36과같은경우 6이하의 1은 제외하고 2 , 4 , 5, 6 으로만 36을 나눠도 소수 판단이 가능하다는 말

 

2*18

3*12

4*9

5x

6*6

7 x

8 x

9*4 반복됨

10 x

11 x

12*3 반복됨

13x

14x

15x

16x

.

.

.

 

6까지만 나눠도 약수 갯수 확인가능... 더 이상해봤자 제한 시간만 늘리는꼴

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	int resultcnt = 0;
	int cnt = 0;
	int N;
	cin >> N;
	for (int i = 2; i <= N; i++)
	{
		int cnt = 0;
		for (int j = 2; j*j <= i; j++)
		{
			if (i%j == 0)
			{
				cnt = 1;
				break;
			}
		}
		if (cnt == 0)
		{
			resultcnt++;
		}
	}
	cout << resultcnt;
}

 

이렇게 바꾸면 제한시간 1초도 안걸림~~ 외워둡시다