10539 - Almost Prime Numbers
Moderator: Board moderators
-
- New poster
- Posts: 17
- Joined: Fri Aug 01, 2003 4:55 pm
- Location: Beijing, China
10539 - Almost Prime Numbers
I first calculate all the prime numbers between 1 and 10<sup>6</sup>
then for every prime numbers below low and high, I add all the log below and high to the base of the prime number as a and b. Then b-a is the answer.
But it is really inefficient, can anyone tell me some efficient algorithm.
I will be very grateful.
then for every prime numbers below low and high, I add all the log below and high to the base of the prime number as a and b. Then b-a is the answer.
But it is really inefficient, can anyone tell me some efficient algorithm.
I will be very grateful.
-
- Guru
- Posts: 647
- Joined: Wed Jun 26, 2002 10:12 pm
- Location: Hong Kong and New York City
- Contact:
I did more or less the same thing, though if you do that, you would probably get something like:
wrong, because you would subtract the same number, while 9 would still be almost-perfect.
Code: Select all
9 9
-
- Experienced poster
- Posts: 151
- Joined: Wed Aug 21, 2002 12:07 am
- Location: Seoul, Korea
- Contact:
Our team had the same problem during the contest.
But ten minutes before the finish, we realized there are only about 80000~ almost primes in the range, so easily generatable & sortable within the time limit. And we could do a binary search on that.
Wondering if this could be better than our last approach we coded that but time was up..
Now I coded that again got AC on 0.2 sec.![:wink:](./images/smilies/icon_wink.gif)
Good luck!
![:-?](./images/smilies/icon_confused.gif)
But ten minutes before the finish, we realized there are only about 80000~ almost primes in the range, so easily generatable & sortable within the time limit. And we could do a binary search on that.
Wondering if this could be better than our last approach we coded that but time was up..
![:wink:](./images/smilies/icon_wink.gif)
Now I coded that again got AC on 0.2 sec.
![:wink:](./images/smilies/icon_wink.gif)
Good luck!
JongMan @ Yonsei
-
- New poster
- Posts: 17
- Joined: Fri Aug 01, 2003 4:55 pm
- Location: Beijing, China
Hi Whinii , I use the method you told me. But the program still runs more than 1 second.
Could you tell me how I can accelerate it?
Many thanks.
Could you tell me how I can accelerate it?
Many thanks.
Code: Select all
#include<iostream>
#include<stdlib.h>
#include<cmath>
using namespace std;
long long alpri[80070];
unsigned int pri[80000];
inline bool isp(int m)
{
for(int i=3;i*i<=m;i+=2)
if (m%i==0) return false;
return true;
}
int cmp1(const void *a, const void *b)
{
long long *aa, *bb;
aa = (long long *)a;
bb = (long long *)b;
if(*aa > *bb)
return 1;
else if(*aa == *bb)
return 0;
else
return -1;
}
int binsearch(long long x)
{
int low = 0;
int high = 80069;
int k;
for(;;)
{
k = (int)(low+high)/2;
if(x < alpri[k] && x < alpri[k - 1])
{
high = k - 1;
continue;
}
if(x > alpri[k] && x > alpri[k + 1])
{
low = k + 1;
continue;
}
if(x >= alpri[k - 1] && x < alpri[k])
return k;
if(x >= alpri[k] && x < alpri[k + 1])
return k + 1;
if(x == alpri[k + 1])
return k + 2;
}
}
int main()
{
int i, c=0, n;
long long a,b;
pri[0]=2;
for(i=3;i<=999984;i+=2)
if(isp(i)) pri[++c]=i;
int d = -1;
for(i = 0; i<=c; i++)
{
long long tmp = pri[i];
while((tmp*=pri[i]) < 1e12)
{
alpri[++d] = tmp;
}
}
qsort(alpri, d, sizeof(long long), cmp1);
cin>>n;
for(int j = 0; j<n; j++)
{
cin>>a>>b;
cout<<binsearch(b) - binsearch(a-1)<<endl;
}
}
Last edited by sharklu2000 on Mon Aug 25, 2003 6:11 pm, edited 1 time in total.
Hello,everybody.
I used an unefficient method:
First search all the prime numbers from 1 to 1000000;
Then write count(x) to caculate number of almost prime numbers
through 1..x;At last using count(high)-count(low-1) to get the answer.
Although it had been accepted,it run during 4+ seconds,that exceeded
the time limit (1 sec)during contest.Can anyone tell me a better method?
I also wrote a binary search version (almost the same as sharklu2000's),
but it also run longer than 2 second,and I got wrong answer.
Larry or Whinii,could you give some detail on programming?
Thank you.
I used an unefficient method:
First search all the prime numbers from 1 to 1000000;
Then write count(x) to caculate number of almost prime numbers
through 1..x;At last using count(high)-count(low-1) to get the answer.
Although it had been accepted,it run during 4+ seconds,that exceeded
the time limit (1 sec)during contest.Can anyone tell me a better method?
I also wrote a binary search version (almost the same as sharklu2000's),
but it also run longer than 2 second,and I got wrong answer.
Larry or Whinii,could you give some detail on programming?
Thank you.
Retired from SJTU Accelerator 2004
-
- New poster
- Posts: 17
- Joined: Fri Aug 01, 2003 4:55 pm
- Location: Beijing, China
Hi,Larry.
I search all the prime numbers first,but the time is still very long.
Here is my c++ code:
Is there anything wrong?
[cpp]
editted
[/cpp]
I search all the prime numbers first,but the time is still very long.
![:(](./images/smilies/icon_frown.gif)
Here is my c++ code:
Is there anything wrong?
[cpp]
editted
[/cpp]
Last edited by hujialie on Tue Aug 26, 2003 9:38 am, edited 2 times in total.
Retired from SJTU Accelerator 2004
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
-
- New poster
- Posts: 17
- Joined: Fri Aug 01, 2003 4:55 pm
- Location: Beijing, China
-
- Experienced poster
- Posts: 146
- Joined: Sat Apr 26, 2003 2:51 am