Prime Time - UVA Online Judge
Problem G: Prime Time
Problem G: Prime Time |
The Problem
Euler is a well-known matematician, and, among many other things, he discovered that the formula n^2 + n + 41 produces a prime for 0 <= n < 40. For n = 40, the formula produces 1681, which is 41 * 41. Even though this formula doesn't always produce a prime, it still produces a lot of primes. It's known that for n <= 10000000, there are 47,5% of primes produced by the formula!
So, you'll write a program that will output how many primes does the formula output for a certain interval.
The Input
Each line of input will be given two positive integer a and b such that 0 <= a <= b <= 10000. You must read until the end of the file.
The Output
For each pair a,b read, you must output the percentage of prime numbers produced by the formula in this interval (a <= n <= b) rounded to two decimal digits (with round half up rule).
Sample Input
0 39 0 40 39 40 1423 2222
Sample Output
100.00 97.56 50.00 44.13
My Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 | #include <stdio.h> #include <math.h> long isprime(long n); long n2n41(long n); int primepct[10001]; int main(int argc, char **argv) { long a, b, i, ip; int notprime, prime; for(i = 0; i < 10001; i++) { primepct[i] = 0; } while (scanf("%ld %ld", &a, &b) != EOF) { for(i = a; i <= b; i++) { if(primepct[i-1]==0) { if(isprime(n2n41(i))==0) { prime++; primepct[i-1] = 1; } else { notprime++; primepct[i-1] = -1; } } else { if(primepct[i-1]==1) { prime++; } else { notprime++; } } } printf("%.2f\n", floor(((double)prime/(prime+notprime))*10000+.5)/100); notprime = 0; prime=0; } return 0; } long n2n41(long n) { return n*n+n+41; } long isprime(long n) { long i = 3; long sqn = 0; while (n%2==0) { n /= 2; return 1; } sqn = (sqrt(n))+1; while (i <= sqn) { if ((n%i)==0) { n /= i; return 1; } else { i += 2; } } return 0; } |
Post new comment