10539  Almost Prime Numbers
Moderator: Board moderators

 Learning poster
 Posts: 53
 Joined: Sat Jul 29, 2006 7:33 am
 Location: (CSE,DU), Dhaka,Bangladesh
10539  Almost Prime Numbers[RTE]
This problem is run time error signal eleven . Here is my code
Plz try to help me.
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;
}
No venture no gain
with best regards

ishtiaq ahmed
with best regards

ishtiaq ahmed

 Experienced poster
 Posts: 147
 Joined: Mon Jun 07, 2010 11:43 am
 Location: University Of Dhaka,Bangladesh
 Contact:
Re: 10539  Almost Prime Numbers
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.
UVa stats: http://felixhalim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/

 Experienced poster
 Posts: 110
 Joined: Tue May 06, 2008 2:18 pm
 Location: CSEDU, Bangladesh
 Contact:
Re: 10539  Almost Prime Numbers
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.
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.
Re: 10539  Almost Prime Numbers
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

 New poster
 Posts: 1
 Joined: Mon Dec 05, 2011 6:51 pm
Re: 10539  Almost Prime Numbers
i understood the problem.
But in what type i took 10^12.
10^12 greater than the long long range
But in what type i took 10^12.
10^12 greater than the long long range
Re: 10539  Almost Prime Numbers
Code: Select all
Accepted
Last edited by raj on Sun Jun 08, 2014 1:25 pm, edited 1 time in total.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10539  Almost Prime Numbers
http://en.wikipedia.org/wiki/Binary_search_algorithm
Java's long data type can handle well over 10^12
http://docs.oracle.com/javase/tutorial/ ... types.html
Java's long data type can handle well over 10^12
http://docs.oracle.com/javase/tutorial/ ... types.html
Check input and AC output for thousands of problems on uDebug!

 New poster
 Posts: 38
 Joined: Wed Dec 05, 2012 11:29 pm
Re: 10539  Almost Prime Numbers
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.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10539  Almost Prime Numbers
Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!

 New poster
 Posts: 38
 Joined: Wed Dec 05, 2012 11:29 pm
Re: 10539  Almost Prime Numbers
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.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10539  Almost Prime Numbers
sqrt and log return a double, try solving it without using them.
Check input and AC output for thousands of problems on uDebug!

 New poster
 Posts: 38
 Joined: Wed Dec 05, 2012 11:29 pm
Re: 10539  Almost Prime Numbers
Got AC. Thanks brianfry713
Re: 10539  Almost Prime Numbers
RuanZheng wrote:I got the same problem with you but now solved. Just don't use log.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 ba is the answer.
But it is really inefficient, can anyone tell me some efficient algorithm.
I will be very grateful.
Just calculate the lower bound and upper bound by brute force
I guess the log costs too much time.
I used log and got accepted in 0.408.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.
So log can be used and it gives accepted.
So i think it is efficient enough to get acc below 1second.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 ba is the answer.
But it is really inefficient, can anyone tell me some efficient algorithm.
I will be very grateful.
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