## 10539 - Almost Prime Numbers

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
There are 80070 almost primes between 1 and 1E12, if memory serves me correctly.

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
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?

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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.

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
The number of primes is 78498. But why almost primes must be the squares of primes - 8 is a almost prime too.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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... =)

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
Thanks, now I understand... I guess the mistake is in long long variables-
in "extended" (Pascal equivalent)
What is the answer for 1 10000 ?

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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

pingus
New poster
Posts: 18
Joined: Sat May 03, 2003 10:33 pm

### CPU Time 0:00.002

Hello

What do you think about that ?

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

one ranklist in 0.002s cpu time

pingus

kathmolla
New poster
Posts: 6
Joined: Tue Nov 30, 2004 2:27 am

### 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.
hey why doing this

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
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
Jalal : AIUB SPARKS

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Yes, for sure there are exactly 80070
almost primes between 1 and 10^12.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

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

``````

RuanZheng
New poster
Posts: 4
Joined: Fri Dec 30, 2005 5:16 pm

### Re: 10539TLE

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.

jainal cse du
New poster
Posts: 23
Joined: Thu Jul 27, 2006 2:43 pm
Location: University of Dhaka,Bangladesh
[Removed]