🙏 15. 소수의 개수(제한시간 1초)

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비 - 인프런 | 강의

강의 저작권으로 인해 문제를 공개하지 않았으며, 답안 코드 혹은 성공한 코드가 작성된 게시글입니다.

15. 소수의 개수(제한시간 1초)

#include <iostream>

using namespace std;

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

강의를 들은 후 다시 짜봤을 때 통과했다.

#include <iostream>

using namespace std;

int main()
{
		int N = 0;
		cin >> N;
	
		int i = 0;
		int j = 0;
		int count = 0;
	
		for (i = 2; i <= N; i++)
		{
				for (j = 2; j <= i; j++)
				{
						if (i % j == 0)
							break;
				}
				if (i == j)
						count++;
		}
		cout << count;
		return 0;
}

처음에 혼자 풀었을 때의 코드이다.

디버깅하면 값은 잘 나오지만 시간초과가 나왔다.

#include <iostream>

using namespace std;

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

그래서 제곱을 하면 더 빨라지기 때문에 잘 실행될 줄 알았으나 아예 틀린 값이 나왔다. 하단에 있는 분기문 때문에 처음 2를 제외한 다른 숫자들은 분기문으로 들어가지 않았다.