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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Jul 25, 2007 2:40 pm

Your code doesnt even pass the samples. Check the input format.
Ami ekhono shopno dekhi...
HomePage

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

10539 - Almost Prime Numbers[RTE]

Post by ishtiaq ahmed » Thu Sep 06, 2007 12:01 am

This problem is run time error signal eleven . Here is my code

Code: Select all

#include<stdio.h>
#include<math.h>

#define NUMBER 1000000
#define SIZE 1000000

int prime[ SIZE ] ;


void generate_prime( void )
{
	int i , j ,flag ; 
	prime[0] = 2  ; prime[1] = 3  ; prime[2] = 5  ; prime[3] = 7  ;
	prime[4] = 11 ; prime[5] = 13 ; prime[6] = 17 ; prime[7] = 19 ;
	int index = 7 ;
	for(i=21 ; i < NUMBER ; i += 2)
	{
		flag = 1 ;
		for(j = 0 ; i * prime[j] <= i ; j++)
		{
			if(i % prime[j] == 0)
			{
				flag = 0 ;
				break ;
			}
		}
		if( flag )
			prime[++ index] = i ;
	}

}


	

void generate_almost_prime( long long start , long long end )
{
	int i=0 , flag = 0 ;
	int sum_start , sum_end ;
	if( start != end)
	{
		sum_start = sum_end = 0;
		for(i= 0 ; prime[i] * prime[i] <= start ; i ++)
			sum_start += (int)( log10( start ) / log10( prime[i] ) ) - 1;
		for(i= 0 ; prime[i] * prime[i] <= end ; i ++)
			sum_end  += (int)( log10( end ) / log10( prime[i] ) ) -  1;
		printf("%d\n" , sum_end - sum_start ) ;
	}
	else
	{
		for(i= 0 ; prime[i] * prime[i] <= start ; i ++)
			if(start % prime[i])
			{
				flag++;
				if(flag == 2 )
					break ;
			}
		if(flag == 1 )
			printf("1\n");
		else
			printf("0\n");
	}

}


int main()
{
	int cas_no ,i ;
	long long start , end ;
	generate_prime() ;
	scanf("%d",&cas_no);
	for(i= 1 ; i <= cas_no ; i++)
	{
		scanf("%lld %lld",&start ,&end);
		generate_almost_prime( start , end );
	}
	return 0;
}
Plz try to help me.
No venture no gain

with best regards
------------------------
ishtiaq ahmed

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10539 - Almost Prime Numbers

Post by Shafaet_du » Sat Sep 04, 2010 10:32 am

You can solve it without binary search. so don't mess up your code with it. generate all the ALMOST PRIMES,store it in an array or vector,and iterate through it.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 10539 - Almost Prime Numbers

Post by zobayer » Thu Mar 10, 2011 8:47 pm

for p and n, there are floor(log(n) / log(p)) powers of p from p to n. this formula can be used as well.
however, in implementation, log and log10 turn out to be too slow, even manual loop takes much much less time. also, one more thing is to note, although it doesn't have any effect on my machine, uva gives WA for log and AC for log10.
so be careful if you like "more mathematical accent" in this problem.
You should not always say what you know, but you should always know what you say.

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 10539 - Almost Prime Numbers

Post by plamplam » Mon Aug 08, 2011 4:26 pm

Well well...it is always better to avoid floating point numbers. I got AC without the use of doubles and it runs fast. btw I agree with Shafet_DU. I got AC in 0.072 seconds without binary search although binary search gets me down to 0.024.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

human_being
New poster
Posts: 1
Joined: Mon Dec 05, 2011 6:51 pm

Re: 10539 - Almost Prime Numbers

Post by human_being » Tue Dec 13, 2011 1:44 pm

i understood the problem.
But in what type i took 10^12.
10^12 greater than the long long range

aamurph
New poster
Posts: 1
Joined: Tue Dec 20, 2011 4:57 pm

Re: 10539 - Almost Prime Numbers

Post by aamurph » Tue Dec 20, 2011 5:49 pm

Don't quite understand your question...

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Re: 10539 - Almost Prime Numbers

Post by raj » Sat Sep 21, 2013 8:17 pm

Code: Select all

Accepted
Last edited by raj on Sun Jun 08, 2014 1:25 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10539 - Almost Prime Numbers

Post by brianfry713 » Mon Sep 23, 2013 10:18 pm

Check input and AC output for thousands of problems on uDebug!

mobarak.islam
New poster
Posts: 38
Joined: Wed Dec 05, 2012 11:29 pm

Re: 10539 - Almost Prime Numbers

Post by mobarak.islam » Mon Dec 09, 2013 7:43 pm

Here I'm getting wrong answer. please help

Code: Select all

Code removed after getting AC 
Last edited by mobarak.islam on Wed Dec 11, 2013 7:45 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10539 - Almost Prime Numbers

Post by brianfry713 » Tue Dec 10, 2013 1:22 am

Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!

mobarak.islam
New poster
Posts: 38
Joined: Wed Dec 05, 2012 11:29 pm

Re: 10539 - Almost Prime Numbers

Post by mobarak.islam » Tue Dec 10, 2013 6:20 am

I solved it without floating point but still getting wrong answer :(

Code: Select all

Code removed after AC
Last edited by mobarak.islam on Wed Dec 11, 2013 7:44 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10539 - Almost Prime Numbers

Post by brianfry713 » Tue Dec 10, 2013 9:45 pm

sqrt and log return a double, try solving it without using them.
Check input and AC output for thousands of problems on uDebug!

mobarak.islam
New poster
Posts: 38
Joined: Wed Dec 05, 2012 11:29 pm

Re: 10539 - Almost Prime Numbers

Post by mobarak.islam » Wed Dec 11, 2013 7:42 am

Got AC. Thanks brianfry713

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10539 - Almost Prime Numbers

Post by lighted » Thu Jul 31, 2014 12:06 am

RuanZheng wrote:
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.
zobayer wrote:for p and n, there are floor(log(n) / log(p)) powers of p from p to n. this formula can be used as well.
however, in implementation, log and log10 turn out to be too slow, even manual loop takes much much less time. also, one more thing is to note, although it doesn't have any effect on my machine, uva gives WA for log and AC for log10.
so be careful if you like "more mathematical accent" in this problem.
I used log and got accepted in 0.408. :D
So log can be used and it gives accepted. :D
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.
So i think it is efficient enough to get acc below 1second. :D

I found all primes in range 1..10^6 -> 78498 primes. For all of them i precalculated their log.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 105 (10500-10599)”