10539 - Almost Prime Numbers

[UFP2161]

There are 80070 almost primes between 1 and 1E12, if memory serves me correctly.

[Dmytro Chernysh]

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]

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]

The number of primes is 78498. But why almost primes must be the squares of primes - 8 is a almost prime too.

[UFP2161]

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]

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]

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]

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]

How can I implement sieve within 0.2 or 0.1 second. My implementation
takes almost 2 seconds. Please help & give a complete description.

[CodeMaker]

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

[Sedefcho]

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]

Yes, for sure there are exactly 80070
almost primes between 1 and 10^12.

[Sedefcho]

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]

I first calculate all the prime numbers between 1 and 10⁶
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]

[Removed]