문제
자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요. 만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다. 제한시간은 1초입니다.
입력설명
첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.
출력설명
첫 줄에 소수의 개수를 출력합니다.
입력예제
20
출력예제
8
#include <stdio.h>
using namespace std;
int main(){
//freopen("input.txt", "rt", stdin);
int n, i, j, count=0;
bool flag;
scanf("%d", &n);
for(i=2; i<=n; i++){
flag = true;
for(j=2; j*j<=i; j++){
if(i%j == 0){
flag = false;
break;
}
}
if(flag == true) count++;
}
printf("%d", count);
return 0;
}
이중for문을 사용해서 i=2; i<=n; i++해서 돌고 j=2; j*j<=i; j++ 하면 제곱근만큼 도는것과 같다.
'알고리즘 > it 취업을 위한 알고리즘 문제풀이' 카테고리의 다른 글
17. 선생님 퀴즈 (0) | 2021.05.17 |
---|---|
16. Anagram(아나그램 : 구글 인터뷰 문제) <algorithm> (0) | 2021.05.17 |
14. 뒤집은 소수 (0) | 2021.05.17 |
13. 가장 많이 사용된 자릿수 (0) | 2021.05.15 |
12. 숫자의 총 개수(large) (0) | 2021.05.15 |