백준 1929 c언어

백준 1929 c언어

작성일 2024.05.12댓글 1건
    게시물 수정 , 삭제는 로그인 필요

코딩 공부하는 학생입니다.
코딩 문제 풀고 있었는데 시간초과가 나와서요...
왜 그런 걸 까요?
감사합니다
#include<stdio.h>
int main() {
int m,n,c=2,nososu=0;
scanf("%d %d",&m,&n);
for(int i=m;i<=n;i++){
while(c!=i){
if(i%c==0){
nososu++;
}
c++;
}
if(nososu==0){
printf("%d\n",i);
}
nososu=0;
c=2;
}
}


#백준 1929 #백준 1929 자바 #백준 1929 파이썬 #백준 1929 c++ #백준 1929 c언어 #백준 1929 시간초과 #백준 1929 python

profile_image 익명 작성일 -

M 과 N의 범위가 100만이기때문에

O(N^2) 의 알고리즘을 적용 할 경우, 이 문제를 시간내에 해결하기 어렵습니다.

가정(100만*100만 번(1조번의 코드를 수행)

O(N log log N ) 알고리즘인

X의 배수를 제거하여 중복처리를 없애는 에라토스테네스의 체를 이용하면 문제를 해결할 수 있습니다.

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

나무위키를 통해서 에라토스테네스의 체를 이해하시는걸 추천 드립니다.

코딩상담,진로상담,학습문의는 카카오채널에서 "은평구 이지코딩"으로 메세지 주세요:)

https://pf.kakao.com/_xldxcrK/chat

백준 1929번을 c언어로 푸는데

안녕하세요 c언어를 배운지 몇 개월된 코린이입니다. 백준 1929번을 푸는데 #include <stdio.h> int main() { int m, n; int arr[1000001] = { 0 }; scanf("%d %d", &m, &n)...