Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# A Solution For The "Carmichael Numbers" Problem

·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views
```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:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.