10200 - Prime Time
Moderator: Board moderators
-
- New poster
- Posts: 1
- Joined: Thu Oct 18, 2001 2:00 am
10200
Is it possible to solve the problem
p10200 " Prime Time " with constant time
?
p10200 " Prime Time " with constant time
?
-
- New poster
- Posts: 17
- Joined: Fri May 31, 2002 6:30 pm
- Contact:
10200
i get time limit exceeded for this question..
what are the possible reason causing it??
and how to solve it???
what are the possible reason causing it??
and how to solve it???
-
- New poster
- Posts: 17
- Joined: Fri May 31, 2002 6:30 pm
- Contact:
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 - '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...^^
[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 - '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...^^
-
- New poster
- Posts: 17
- Joined: Fri May 31, 2002 6:30 pm
- Contact:
-
- New poster
- Posts: 17
- Joined: Fri May 31, 2002 6:30 pm
- Contact:
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]
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]
10200 I have WA
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.
Please, send me such n that 1000 < n < 9999 and the value n*n + n + 41 is prime.
-
- New poster
- Posts: 12
- Joined: Mon Jul 29, 2002 3:04 pm
- Contact:
Not the fastest method, but will get a accepted.
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
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
![:D](./images/smilies/icon_biggrin.gif)
My 2 cents worth
WA!
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=1;
while(scanf("%d %d",&a,&b)==2){
pr=0;
for (i=a;i<=b;i++)
if (isp==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.
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=1;
while(scanf("%d %d",&a,&b)==2){
pr=0;
for (i=a;i<=b;i++)
if (isp==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.
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;
}
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;
}