Page 3 of 3
Posted: Wed Jul 25, 2007 2:40 pm
by Jan
Your code doesnt even pass the samples. Check the input format.
10539 - Almost Prime Numbers[RTE]
Posted: Thu Sep 06, 2007 12:01 am
by ishtiaq ahmed
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.
Re: 10539 - Almost Prime Numbers
Posted: Sat Sep 04, 2010 10:32 am
by Shafaet_du
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.
Re: 10539 - Almost Prime Numbers
Posted: Thu Mar 10, 2011 8:47 pm
by zobayer
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.
Re: 10539 - Almost Prime Numbers
Posted: Mon Aug 08, 2011 4:26 pm
by plamplam
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.
Re: 10539 - Almost Prime Numbers
Posted: Tue Dec 13, 2011 1:44 pm
by human_being
i understood the problem.
But in what type i took 10^12.
10^12 greater than the long long range
Re: 10539 - Almost Prime Numbers
Posted: Tue Dec 20, 2011 5:49 pm
by aamurph
Don't quite understand your question...
Re: 10539 - Almost Prime Numbers
Posted: Sat Sep 21, 2013 8:17 pm
by raj
Re: 10539 - Almost Prime Numbers
Posted: Mon Sep 23, 2013 10:18 pm
by brianfry713
Re: 10539 - Almost Prime Numbers
Posted: Mon Dec 09, 2013 7:43 pm
by mobarak.islam
Here I'm getting wrong answer. please help
Re: 10539 - Almost Prime Numbers
Posted: Tue Dec 10, 2013 1:22 am
by brianfry713
Try solving it without using floating point.
Re: 10539 - Almost Prime Numbers
Posted: Tue Dec 10, 2013 6:20 am
by mobarak.islam
I solved it without floating point but still getting wrong answer
Re: 10539 - Almost Prime Numbers
Posted: Tue Dec 10, 2013 9:45 pm
by brianfry713
sqrt and log return a double, try solving it without using them.
Re: 10539 - Almost Prime Numbers
Posted: Wed Dec 11, 2013 7:42 am
by mobarak.islam
Got AC. Thanks brianfry713
Re: 10539 - Almost Prime Numbers
Posted: Thu Jul 31, 2014 12:06 am
by lighted
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
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.
So log can be used and it gives accepted.
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.
I found all primes in range 1..10^6 -> 78498 primes. For all of them i precalculated their log.