글 읽기 - 에라토스테네스의 체 알고리즘 런타임 에러 질문

dmswl022329 2년 전 0

erstos 함수에 400000 이상의 수를 넣으면 런타임 에러가 뜹니다.

어떤이유에서 이런지 이해가 안갑니다.

#include<bits/stdc++.h>
#define ll long long
using namespace std;

bool num[4004010];
void eratos(int N){
    for(int i=2;i<N;i++)num[i] = true;
    for(int i=2;i<N;i++){
        if(num[i]){
            for(int j=i*i;j<N;j += i){
            	// cout << j << "\n";
                num[j]=false;
            }
        }
    }
}


int main() {
	ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
	eratos(400000);
	for(int i = 0; i < 1000; i++) if(num[i]) cout << i << "\n";
	return 0;
}

djm03178 2년 전 0

i가 int이기 때문에 46341 이상부터는 제곱을 하면 int의 범위를 벗어나 오버플로우가 됩니다. i와 j 모두 long long을 사용해야 합니다.

dmswl022329 2년 전 0

i의 범위를 sqrt(N) 까지 해야하는걸 질문 올리고 깨달았네요

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

에라토스테네스의 체 알고리즘 런타임 에러 질문

dmswl022329 2년 전 0

djm03178 2년 전 0

dmswl022329 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말