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

sharklu2000
New poster
Posts: 17
Joined: Fri Aug 01, 2003 4:55 pm
Location: Beijing, China

10539 - Almost Prime Numbers

Post by sharklu2000 » Mon Aug 25, 2003 4:59 am

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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Aug 25, 2003 5:03 am

I did more or less the same thing, though if you do that, you would probably get something like:

Code: Select all

9 9
wrong, because you would subtract the same number, while 9 would still be almost-perfect.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Mon Aug 25, 2003 5:25 am

Our team had the same problem during the contest. :-?

But ten minutes before the finish, we realized there are only about 80000~ almost primes in the range, so easily generatable & sortable within the time limit. And we could do a binary search on that.

Wondering if this could be better than our last approach we coded that but time was up.. :wink:

Now I coded that again got AC on 0.2 sec. :wink:
Good luck!
JongMan @ Yonsei

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Aug 25, 2003 6:19 am

Ya, with my old algo, I had it AC in 6.3 seconds, but I didn't realize I could binary search, and after my friend (UFP), told me, I did it and got it AC in 0.2 secs too..

And then I kicked myself for not remembering.. heh

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

Post by UFP2161 » Mon Aug 25, 2003 7:39 am

Yeah.. that would be me.. the logs were getting too messy and slow and my computer kept producing slight floating point errors on them, so I began thinking about the problem in reverse and it worked out much better =)

Still need a faster sieve though =P

sharklu2000
New poster
Posts: 17
Joined: Fri Aug 01, 2003 4:55 pm
Location: Beijing, China

Post by sharklu2000 » Mon Aug 25, 2003 8:56 am

Hi Whinii , I use the method you told me. But the program still runs more than 1 second.
Could you tell me how I can accelerate it?
Many thanks.

Code: Select all

#include<iostream>
#include<stdlib.h>
#include<cmath>
using namespace std;
long long alpri[80070];
unsigned int pri[80000];
inline bool isp(int m)
{
	for(int i=3;i*i<=m;i+=2)
		if (m%i==0) return false;
	return true;
}
int cmp1(const void *a, const void *b)
{
	long long *aa, *bb;
	aa = (long long *)a;
	bb = (long long *)b;
	if(*aa > *bb)
		return 1;
	else if(*aa == *bb)
		return 0;
	else
		return -1;
}

int binsearch(long long x)
{
	int low = 0;
	int high = 80069;
	int k;
	for(;;)
	{
		k = (int)(low+high)/2;
		if(x < alpri[k] && x < alpri[k - 1])
		{
			high = k - 1;
			continue;
		}
		if(x > alpri[k] && x > alpri[k + 1])
		{
			low = k + 1;
			continue;
		}
		if(x >= alpri[k - 1] && x < alpri[k])
			return k;
		if(x >= alpri[k] && x < alpri[k + 1])
			return k + 1;
		if(x == alpri[k + 1])
			return k + 2;
	}
}

int main()
{
	int i, c=0, n;
	long long a,b;
	pri[0]=2;
	for(i=3;i<=999984;i+=2)
		if(isp(i)) pri[++c]=i;
	int d = -1;
	for(i = 0; i<=c; i++)
	{
		long long tmp = pri[i];
		while((tmp*=pri[i]) < 1e12)
		{
			alpri[++d] = tmp;
		}
	}

	qsort(alpri, d, sizeof(long long), cmp1);
	cin>>n;
	for(int j = 0; j<n; j++)
	{
		cin>>a>>b;
		cout<<binsearch(b) - binsearch(a-1)<<endl;
	}

}
Last edited by sharklu2000 on Mon Aug 25, 2003 6:11 pm, edited 1 time in total.

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

Post by hujialie » Mon Aug 25, 2003 9:54 am

Hello,everybody.

I used an unefficient method:
First search all the prime numbers from 1 to 1000000;
Then write count(x) to caculate number of almost prime numbers
through 1..x;At last using count(high)-count(low-1) to get the answer.

Although it had been accepted,it run during 4+ seconds,that exceeded
the time limit (1 sec)during contest.Can anyone tell me a better method?

I also wrote a binary search version (almost the same as sharklu2000's),
but it also run longer than 2 second,and I got wrong answer.

Larry or Whinii,could you give some detail on programming?

Thank you.
Retired from SJTU Accelerator 2004

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Aug 25, 2003 12:42 pm

Use sieve first to generate prime table, then for each prime, generate all the almost primes.

Sort and binary search.. that's all I did.

(I binary searched to get the count to low, than the count to high, then subtract them..)

Ya, so sharklu, run a sieve first, and tell me if it helps that much..

sharklu2000
New poster
Posts: 17
Joined: Fri Aug 01, 2003 4:55 pm
Location: Beijing, China

Post by sharklu2000 » Mon Aug 25, 2003 1:49 pm

Hi Larry, what do you mean by using sieve first. :oops:
Is it precomputing all the primes in the range?
Could you tell more in detail about sieve? Thanks.

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

Post by UFP2161 » Mon Aug 25, 2003 4:25 pm

Just lookup "Sieve of Eratosthenes" on google.

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

Post by hujialie » Mon Aug 25, 2003 4:38 pm

Hi,Larry.

I search all the prime numbers first,but the time is still very long. :(
Here is my c++ code:
Is there anything wrong?


[cpp]
editted
[/cpp]
Last edited by hujialie on Tue Aug 26, 2003 9:38 am, edited 2 times in total.
Retired from SJTU Accelerator 2004

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Mon Aug 25, 2003 4:58 pm

you dont need to store prime number. while doing sieve, generate almost primes number. :) :) :)
i did not use binary search (just sequential search), but got AC in 0.7 sec :) :)
hope it helps :)

regards,
titid gede
Kalo mau kaya, buat apa sekolah?

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

Post by hujialie » Mon Aug 25, 2003 5:59 pm

Thank you titd_gede,UFP2161 and Larry.
Now I got accepted within 0.5 seconds.
Retired from SJTU Accelerator 2004

sharklu2000
New poster
Posts: 17
Joined: Fri Aug 01, 2003 4:55 pm
Location: Beijing, China

Post by sharklu2000 » Mon Aug 25, 2003 6:51 pm

Thanks UFP2161, Larry, Whinii F.
I got acc with 0.4se now.

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

Post by Dmytro Chernysh » Thu Aug 28, 2003 4:11 pm

How many almost prime numbers are? I got 573 for 1..10^12.
And it's wrong...

Post Reply

Return to “Volume 105 (10500-10599)”