http://snippets.dzone.com/posts Sun, 12 Oct 2008 14:39:57 GMT DZone Snippets: 10006 code http://snippets.dzone.com/posts/show/5429 A solution for the "Carmichael Numbers" problem. <br /> <br />Problem description: <br /><a href="http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10006.html">http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10006.html</a> <br /> <br />Author: <a href="http://joanatrindade.wikidot.com">Joana Matos Fonseca da Trindade</a> <br />Date: 2008.04.24 <br /> <br /><code> <br />/* <br /> * Solution for "Carmichael Numbers" problem. <br /> * UVa ID: 10006 <br /> */ <br />#include <iostream> <br />#include <math.h> <br /> <br />#define MAXPRIME 65001 <br /> <br />using namespace std; <br /> <br />/* <br /> * Modular exponentiation algorithm. Returns b^e mod m. <br /> */ <br />unsigned long long fast_mod_pow(unsigned long long b, unsigned long long e, unsigned long long m) { <br /> unsigned long long r = 1; <br /> while (e > 0) { <br /> if ((e & 1) == 1) { <br /> r = (r * b) % m; <br /> } <br /> e >>= 1; <br /> b = (b * b) % m; <br /> } <br /> return r; <br />} <br /> <br />/* <br /> * Generates all prime numbers up to MAXPRIME. Based on <br /> * the Sieve of Eratosthenes. <br /> */ <br />void gen_primes(bool p[]) { <br /> p[0] = p[1] = false; <br /> <br /> /* <br /> * starting at number 2 and going to the upper limit, mark <br /> * all numbers as potential primes <br /> */ <br /> for (int i=2; i<MAXPRIME; i++) { <br /> p[i] = true; <br /> } <br /> <br /> int m = floor(sqrt(MAXPRIME)); <br /> int n; <br /> /* <br /> * mark all multiples of a prime as non-primes. this has to be done for primes <br /> * only up to the square root, since every number in the array has at least <br /> * one factor smaller than the square root of the limit. <br /> */ <br /> for (int i=2; i<m; i++) { <br /> if (p[i]) { <br /> n = MAXPRIME / i; <br /> for (int j=2; j<=n; j++) { <br /> p[i * j] = false; <br /> } <br /> } <br /> } <br />} <br /> <br />/* generates all carmichael numbers up to the given limit by performing the fermat test */ <br />void gen_carmi(bool c[], bool p[]) { <br /> <br /> /* initialize carmichael numbers array with false */ <br /> memset(c, 0, MAXPRIME * sizeof(bool)); <br /> <br /> /* <br /> * starting from the first non-prime, mark all <br /> * odd numbers as potential carmichael numbers <br /> */ <br /> for (int i=9; i<MAXPRIME; i+=2) { <br /> c[i] = true; <br /> } <br /> <br /> /* <br /> * again, for all odd numbers, we exclude the primes and perform <br /> * the fermat test for 2 <= a <= n-1. <br /> */ <br /> for (int n=9; n<MAXPRIME; n+=2) { <br /> /* VERY IMPORTANT! check first if this number is prime, otherwise we get TLE */ <br /> if (p[n]) { <br /> c[n] = false; <br /> continue; <br /> } <br /> for (int a=2; a<=n-1; a++) { <br /> if (fast_mod_pow(a,n,n) != a) { <br /> c[n] = false; <br /> break; <br /> } <br /> } <br /> } <br />} <br /> <br />/* main */ <br />int main() { <br /> unsigned long long n; /* number */ <br /> unsigned long long a; /* a of the fermat test */ <br /> bool prime[MAXPRIME]; /* prime numbers array */ <br /> bool carmi[MAXPRIME]; /* carmichael numbers array */ <br /> <br /> gen_primes(prime); <br /> gen_carmi(carmi, prime); <br /> <br /> while (cin >> n && (n != 0)) { <br /> if (carmi[n]) { <br /> cout << "The number " << n << " is a Carmichael number." << endl; <br /> } else { <br /> cout << n << " is normal." << endl; <br /> } <br /> } <br /> return 0; <br />} <br /></code> Thu, 24 Apr 2008 23:16:02 GMT http://snippets.dzone.com/posts/show/5429 jmftrindade (Joana M. F. da Trindade)