10539  Almost Prime Numbers
Moderator: Board moderators

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am
I didn't say it was amount of almost primes is the number of primes squared, just that this is the minimal amount of almost primes. So, if you have 78498 primes, that means there are at least 78498 almost primes. Now you just have to add cubes, ^4, ^5, etc. Just as long as you understand why there aren't just 573 almost primes... =)

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am
CPU Time 0:00.002
Hello
What do you think about that ?
http://acm.uva.es/cgibin/OnlineJudge?ProblemStat:10539
one ranklist in 0.002s cpu time
pingus
What do you think about that ?
http://acm.uva.es/cgibin/OnlineJudge?ProblemStat:10539
one ranklist in 0.002s cpu time
pingus
how to implement sieve
How can I implement sieve within 0.2 or 0.1 second. My implementation
takes almost 2 seconds. Please help & give a complete description.
takes almost 2 seconds. Please help & give a complete description.
hey why doing this

 Experienced poster
 Posts: 183
 Joined: Thu Nov 11, 2004 12:35 pm
 Location: AIUB, Bangladesh
Well, I don't know how you have implemented it in your code...but I can give u a hint , though it may not do much boost but did you imcrement by 2?
you know primes are always odd numbers except 2.
so if you consider the case for 2 and then starting from 3 and incrementing the loop counter by 2 may cause it work bit faster.
This is the most basic booster, additional proning can be done but that is implemetation dependent.
That what I use.....and dont think that I m a smart person who can give you the best algo, I tried to help you with as much as I know
you know primes are always odd numbers except 2.
so if you consider the case for 2 and then starting from 3 and incrementing the loop counter by 2 may cause it work bit faster.
This is the most basic booster, additional proning can be done but that is implemetation dependent.
Code: Select all
for(int i=4;i<=MAX;i+=2)
{
prime[i]++;
}
for(i=3;i<=sqrt(MAX);i+=2)
{
if(!prime[i])
{
for(j=i*i;j<=MAX;j+=i)
{
prime[j]++;
}
}
}
Jalal : AIUB SPARKS
The sequence of the almost primes between 1 and 10^12
( if we look at it in increasing order of its elements )
starts with these numbers:
Code: Select all
4
8
9
16
25
27
32
49
64
81
121
125
128
169
243
256
289
343
361
512
529
625
729
841
961
1024
1331
1369
...
...
...
Code: Select all
...
...
...
999706021609
999726018769
999766013689
999814008649
999834006889
999862004761
999906002209
999918001681
999922001521
999958000441
999966000289
Re: 10539TLE
I got the same problem with you but now solved. Just don't use log.sharklu2000 wrote: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 ba is the answer.
But it is really inefficient, can anyone tell me some efficient algorithm.
I will be very grateful.
Just calculate the lower bound and upper bound by brute force
I guess the log costs too much time.

 New poster
 Posts: 23
 Joined: Thu Jul 27, 2006 2:43 pm
 Location: University of Dhaka,Bangladesh