글 읽기 - 1456번 거의 소수

supernova 9년 전 0

이 문제에서 A와 B의 차이는 몇정도로 생각하면 되나요?

pichulia 9년 전 1

대충 10^14정도 차이가 난다고 생각하시고 푸시면 됩니다.

supernova 9년 전 0

그러면 당연히 이런식으로하면 시간초과에 세그멘테이션 오류겠네요?

#include<stdio.h>
bool check[50000000];
int isPrime[1000011], cnt , Prime[100000];
long long int n, m, res;

void getPrime(){
 long long int num = 2;
 for( ; num < 1000011 ; num++){
 if(isPrime[num] == true) continue;

 for(long long int j = num * num; j < 1000011; j += num){
 isPrime[j] = true;
 }
 }

 for(int i = 2 ; i < 1000011 ; i++)
 if(isPrime[i] == false)
 Prime[cnt++] = i;
}

void getNumberOfAlmostPrime(){
 getPrime();
 for(int j = 0 ; j < cnt ; j++){
 long long int num = Prime[j] * Prime[j];

 for( ; num <= m; num *= Prime[j]){
 if(num < n) continue;
 check[num - n] = true;
 }
 }
 int last = m - n ;

 for(int i = 0 ; i < last; i++)
 if(check[i] == true) res++;
}

int main(){
 scanf("%lld %lld",&n,&m);

 getNumberOfAlmostPrime();

 printf("%lld\n",res);

 return 0;
}

supernova 9년 전 0

어떤식으로 풀어야할까요? @pichulia

pichulia 9년 전 1

방법은 맞으셨네요

res++;를 나중에 하시지마시고

check배열 true로 만들 때 바로 더해버리세요ㅋㅋ 같은 수가 서로 다른 소수의 n승으로 표현되버려서 한 숫자에 대해 중복되서 더해진다면 문제가 되겠지만....그런 일이 없으니까요.ㅋㅋㅋ

그리고 소수구할 때 1000011이 아니라10000011까지 숫자 제한을 늘려보시길...

supernova 9년 전 1

와 감사합니다 ㅎㅎㅎㅎㅎ 근데 틀렸어요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

pichulia 9년 전 2

틀린 이유는 간단합니다. 10^14 인 숫자 m과 10^7인 소수를 곱하면 10^21정도되는 수가 나옵니다. (코드상에서는 num *= Prime[i] 이부분) 즉 long long int 범위를 벗어나는 숫자때메 생기는 오버플로우때매 틀렸을 것입니다.

이 곱셈에 의한 오버플로우를 발생시키지 않고 해결하는 것이 숨겨진 문제 되시겠습니다!ㅋㅋ

supernova 9년 전 1

아... 그럼 big integer를 구현해야한다는 말씀인가요? ㅠㅠㅠㅠ 우와 문제 한번 ...;;하하하..;;;

pichulia 9년 전 5

if(a*b <= m) <==> if(a <= m / b)

big integer 구현이라는 뻘짓을 구경할 순 없어서 천기누설하고 갑니다.

참고로 부등식에 등호 없으면 성립 안함...

supernova 9년 전 0

안그래도 빅인티져 구현해도 어떻게 하지라고 생각하고 있었는데 ㅋㅋㅋㅋㅋ

감사합니다 @pichulia님

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