10200 - Prime Time

[Maswood Hasan Mostafi]

Is it possible to solve the problem
p10200 " Prime Time " with constant time
?

[Casimiro]

Hi!

Well, only if you do some sort of precalculation. Otherwise, the primality test could be done in constant time too...

Best Regards, Casimiro

[Melon Melon]

i get time limit exceeded for this question..
what are the possible reason causing it??
and how to solve it???

[10153EN]

Or could you tell us what your algorithm is?

I solve this by using an array of prime numbers.

[Melon Melon]

The following is the way i solve it....
[c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BASE 1000000

int main(int argv, char *argc[])
{
unsigned *factorial;
int n, size, i, j;
int sum, length;
char str[7];

while(scanf("%d", &n) != EOF)
{
size = 1;

factorial = (unsigned *)malloc(sizeof(unsigned));
if (factorial == NULL)
exit(1);

*factorial = 1;

/* Calculate the factorial */
for(i = 2; i <= n; i++)
{
/* Multiplication */
for(j = 0; j < size; j++)
*(factorial + j) *= i;

/* Promote the extra digits when overflow */
for(j = 0; j < size - 1; j++)
{
if(*(factorial + j) >= BASE)
{
*(factorial + j + 1) += *(factorial + j) / BASE;
*(factorial + j) %= BASE;
}
}

/* Add one more variable to hold the value when needed */
if(*(factorial + size - 1) >= BASE)
{
size++;
factorial = (unsigned *)realloc(factorial, sizeof(unsigned) * size);

if(factorial == NULL)
exit(1);

*(factorial + size - 1) = *(factorial + size - 2) / BASE;
*(factorial + size - 2) %= BASE;
}
}

length = sprintf(str, "%u", *(factorial + size - 1));
sum = 0;
for(i = 0; i < length; i++)
sum += str[i] - '0';
for(i = size - 2; i>= 0; i--)
{
length = sprintf(str, "%06u", *(factorial + i));
for(j = 0; j < length; j++)
sum += str[j] - '0';
}
printf("%d\n", sum);

free(factorial);
}

return 0;
}

[/c]


where is the bug????
btw..i wonder how you solve it by prime number..??
ths ths...^^

[10153EN]

Are you asking for the wrong problem number? 10200 is Prime Time, so it's not strange (in other words, a normal way) to solve it by prime numbers.

[Melon Melon]

O...
sorry that i ask wrongly..
the question no should be 10220...........

[10153EN]

Never mind~

Would the base you used too large? base 100000 would cause overflow if two large numbers < 100000 are multiplied...

[Melon Melon]

my problem solved.....
ths ths.......

[bundy]

I am getting a time out on this problem. One post said he used an array of prime numbers.. doesn't that kind of defeat the purpose? I know I don't have my output formatted correctly but I am working on spee frist.

Here is my code.

[cpp]#include <iostream>
#include <cmath>

using namespace std;

const INPUT_MAX = 10000;
const INPUT_MIN = 0;

bool isPrime(double &d);

int main()
{
int a;
int b;

while (cin >> a >> b)
{

int formulaCorrect = 0;
double i;
double numbersTested = 0;

if ( a < INPUT_MIN ||
a > b ||
b > INPUT_MAX)
return 0;

for (i = a; i <= b; i++)
{

double formulaValue;
formulaValue = pow(i,2) + i + 41;

if (isPrime(formulaValue))
formulaCorrect++;
numbersTested++;
}

//cout << "formula correct = " << formulaCorrect << "\tCount = " << i << endl;
cout << formulaCorrect / numbersTested * 100.00 << endl;
}

return 0;
}

bool isPrime(double &d)
{

bool prime = true;

for (int i = 4; i < d/2; i++)
{
if (long(d) % i == 0)
{
prime = false;
break;
}
}

// cout << d << " prime value = " << prime << endl;

return prime;
}[/cpp]

[medv]

To my suprise my program says that there is no prime numbers among values n*n + n + 41 for 1000 < n < 9999. I think I am wrong when testing the primes.
Please, send me such n that 1000 < n < 9999 and the value n*n + n + 41 is prime.

[Daniel Chia]

Your code will get accepted with slight modifications.
The main redundancy there is repeatedly checking certain n.
for example, the input set
0 300
0 10000
will regenerate all the numbers from 0 to 300.
As such, you should pre-generate and check for primality all the numbers.
After which, just loop through and do some counting thats how i did it anyway

My 2 cents worth

[Ming Han]

I don't get time limit exceeded now, but I get wrong answer?

Any suggestions?

[cpp]// ACM Problem 10200
// Prime Time
// Done by Teh Ming Han

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

int prime(unsigned long num){
for (long b=3; b<=int(sqrt(num)); b+=2)
if (num % b == 0) return 0;
return 1;
}

int main(){
unsigned int a,b,i;
unsigned long per,pr,total;
int isp[10001] = {0};

for (i=0;i<=10000;i++) //pre-generate
if (prime(i*i+i+41)==1) isp[i]=1;

while(scanf("%d %d",&a,&b)==2){
pr=0;
for (i=a;i<=b;i++)
if (isp[i]==1) pr++;
per = (pr*100000)/(b-a+1);
if (per%10>5){
per = int(per/10);
per++;
}else{
per = int(per/10);
}
printf("%d.",int(per/100));
per = int(per%100);
if (per==0) printf("00\n");
else if (per<10) printf("0%d\n",per);
else printf("%d\n",per);
}
return 0;
}[/cpp]

Thanks a lot.

[Larry]

Precal the check for all the numbers generated, so you don't have to keep checking for each input.

[yahoo]

I have used brute force method to solve this but getting runtime error all the time.Can anybody please explain why i am getting runtime error.
Here is my code:
#include <stdio.h>
#include <math.h>

main()
{
long long int i,j,hi,lo,r,a[100000],pr,cnt,n=0,flag,num;
double count;
for(i=2;i<10000;i++)
{
for(j=2;j<=i/2;j++)
if(!(i%j))
break;
if(j<=i/2);else a[n++]=i;
}
while(1)
{
r=scanf("%lld%lld",&hi,&lo);
if(r==EOF) break;
cnt=0;
for(i=hi;i<=lo;i++)
{
pr=i*i+i+41;
j=flag=0;
while(1)
{
if(pr%a[j]==0) {flag=1;break;}
if(a[j]>pr/2) break;
j++;
}
if(!flag) cnt++;
}
num=lo-hi+1;
count=((float)cnt)/num*100;
printf("%.2lf\n",count);
}
return 0;
}