Over a million developers have joined DZone.

A Solution For The "Carmichael Numbers" Problem

·
A solution for the "Carmichael Numbers" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10006.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.24


/* 
 * Solution for "Carmichael Numbers" problem.
 * UVa ID: 10006
 */
#include 
#include 

#define MAXPRIME 65001

using namespace std;

/*
 * Modular exponentiation algorithm. Returns b^e mod m.
 */
unsigned long long fast_mod_pow(unsigned long long b, unsigned long long e, unsigned long long m) {
    unsigned long long r = 1;
    while (e > 0) {
        if ((e & 1) == 1) {
	    r = (r * b) % m;
        }
        e >>= 1;
        b = (b * b) % m;
    }
    return r;
}

/* 
 * Generates all prime numbers up to MAXPRIME. Based on
 * the Sieve of Eratosthenes.
 */
void gen_primes(bool p[]) {
    p[0] = p[1] = false;
	
    /* 
     * starting at number 2 and going to the upper limit, mark 
     * all numbers as potential primes 
     */  
    for (int i=2; i> n && (n != 0)) {	
        if (carmi[n]) {
            cout << "The number " << n << " is a Carmichael number." << endl;
        } else {
            cout << n << " is normal." << endl;
        }
    }
    return 0;
}
Topics:

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}