루트값 까지 배수를 제외해서 소수값 구하는방법

#include<iostream> using namespace std; bool arr[1000000];//소수인지 확인할 배열(인덱스가 소수인지 확인할 값이다) void chee(int num){ for(int j=2;j<1000/*arr배열의 최대값의 루트 값가지만 나누어보면 된다*/;j++){ if(!arr[j])//만약 arr[j]가 제외되었던 숫자면 다시 안해도 된다.(2로 한번 나누고 나면 4는 안해도됨) for(int i=2;i*j<1000000;i++){//2부터 배열의 최대값까지 j의 배수들은 나눈다. //(즉 1이 아닌 다른 수로 나누어진다는 의미이므로 소수가 아니기 떄문에..) arr[i*j]=1;//각 배수에 true로 표시해준다. } } } int main(){ int num; cin>>num;//소수인지 확인 하고 싶은 숫자 입력 chee(num); if(arr[num] == 0 ) cout << "소수"<<endl;//false값들은 2부터 해당값가지 배수가 없는것이므로 소수이다. else cout << "not 소수"<<endl; return 0; }