Page 2 of 3
Posted: Thu Aug 28, 2003 4:33 pm
There are 80070 almost primes between 1 and 1E12, if memory serves me correctly.

Posted: Thu Aug 28, 2003 4:42 pm
But I can see almost prime numbers like:
4,8,16,32...,9,27,81,243,...,25,652,... so only powers of prime numbers.
So why 80070?

Posted: Thu Aug 28, 2003 4:58 pm
Well, first, how many primes do you find below 10E6? So, if you square each one, you get an almost prime less than 10E12, correct? So, that's should be lower bound for the number of almost primes.

Also, make sure you're using C long long or an equivalent type in Pascal/Java.

Posted: Thu Aug 28, 2003 5:30 pm
The number of primes is 78498. But why almost primes must be the squares of primes - 8 is a almost prime too.

Posted: Thu Aug 28, 2003 5:59 pm
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... =)

Posted: Thu Aug 28, 2003 6:10 pm
Thanks, now I understand... I guess the mistake is in long long variables-
in "extended" (Pascal equivalent)
What is the answer for 1 10000 ?

Posted: Thu Aug 28, 2003 6:25 pm
13

1 1
1 10
1 100
1 1000
1 10000
1 100000
1 1000000
1 10000000
1 100000000
1 1000000000
1 10000000000
1 100000000000
1 1000000000000
0
3
10
25
51
108
236
555
1404
3689
10084
28156
80070

### CPU Time 0:00.002

Posted: Wed Sep 03, 2003 12:55 am
Hello

What do you think about that ?

http://acm.uva.es/cgi-bin/OnlineJudge?ProblemStat:10539

one ranklist in 0.002s cpu time pingus

### how to implement sieve

Posted: Sat Dec 25, 2004 7:10 pm
How can I implement sieve within 0.2 or 0.1 second. My implementation

Posted: Sat Jan 01, 2005 7:21 am 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.

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]++;
}
}
}
``````
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 Posted: Wed Feb 23, 2005 6:01 pm
My program says we have 80070
almost primes in the range [1 ... 10^12].

Of course the number 1 is not almost prime.
And the number 10^12 is also not almost prime.

Posted: Wed Feb 23, 2005 7:18 pm
Yes, for sure there are exactly 80070
almost primes between 1 and 10^12.

Posted: Wed Feb 23, 2005 7:26 pm

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
...
...
...
``````
and it ends with these numbers

Code: Select all

``````...
...
...
999706021609
999726018769
999766013689
999814008649
999834006889
999862004761
999906002209
999918001681
999922001521
999958000441
999966000289

``````

### Re: 10539TLE

Posted: Sun Jul 01, 2007 4:53 pm
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 b-a is the answer.
But it is really inefficient, can anyone tell me some efficient algorithm.
I will be very grateful.
I got the same problem with you but now solved. Just don't use log.
Just calculate the lower bound and upper bound by brute force I guess the log costs too much time.

Posted: Tue Jul 24, 2007 3:57 pm
[Removed]