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

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Thu Aug 28, 2003 4:33 pm

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

Post by Dmytro Chernysh » 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?

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » 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.

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

Post by Dmytro Chernysh » 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.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » 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... =)

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

Post by Dmytro Chernysh » 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 ?

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » 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

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

CPU Time 0:00.002

Post by pingus » 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 :o

pingus

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

how to implement sieve

Post by kathmolla » Sat Dec 25, 2004 7:10 pm

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

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » 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 :)
Jalal : AIUB SPARKS

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

Post by Sedefcho » 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.

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

Post by Sedefcho » Wed Feb 23, 2005 7:18 pm

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

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

Post by Sedefcho » 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


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

Re: 10539TLE

Post by RuanZheng » 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 :D
I guess the log costs too much time.

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

Post by jainal cse du » Tue Jul 24, 2007 3:57 pm

[Removed]

Post Reply

Return to “Volume 105 (10500-10599)”