Page **4** of **5**

### Re: 10006 - Carmichael Numbers

Posted: **Tue Sep 09, 2008 7:32 am**

by **Moshiur Rahman**

reply for adhoc17......

Your program returns 62 Carmichael Numbers in the input range, while there are only 15

for example 341,645,....60787 are not a Carmichael Numbers, but your program says they are also Carmichael numbers

your isprime() function does not work for numbers which are a power of two, like 4,8,16 etc.

check your expm() function again....

### Re: 10006 - Carmichael Numbers

Posted: **Wed Feb 11, 2009 2:22 pm**

by **alirezanoori**

I can't understand the problem. Why 17 is Normal?

2^17 mod 17 = 2

3^17 mod 17 = 3

4^17 mod 17 = 4

5^17 mod 17 = 5

6^17 mod 17 = 6

7^17 mod 17 = 7

8^17 mod 17 = 8

9^17 mod 17 = 9

10^17 mod 17 = 10

11^17 mod 17 = 11

12^17 mod 17 = 12

13^17 mod 17 = 13

14^17 mod 17 = 14

15^17 mod 17 = 15

16^17 mod 17 = 16

Although my program finds all these numbers, I double checked them with windows calculator. And I'm sure they're correct.

Could you please help me? I'm sure something's here that I can't understand!

### Re: 10006 - Carmichael Numbers

Posted: **Wed Feb 11, 2009 4:05 pm**

by **mf**

Quote from problem statement:

Some numbersthat are **not prime** still pass the Fermat test with every number smaller than themselves. These numbers are called Carmichael numbers.

17 is a prime.

### Re: 10006 - Carmichael Numbers

Posted: **Wed Feb 11, 2009 11:30 pm**

by **alirezanoori**

well, first of all thanks for your help. I finally understand the problem. I just don't know how I get WA!!! Because I'm almost sure I've done anything OK. I've checked my output format and its OK too. Here's my Fermat function.

If there is ANYTHING wrong with it please let me know. Thanks.

### Re: 10006 - Carmichael Numbers

Posted: **Thu Feb 12, 2009 9:38 am**

by **mf**

I don't see anything wrong with it.

Try to run your program on all possible 65000 inputs, and check that it identifies only these numbers as Carmichael numbers -

http://www.research.att.com/~njas/seque ... 2997&fmt=4

### Re: 10006 - Carmichael Numbers

Posted: **Thu Feb 12, 2009 5:55 pm**

by **alirezanoori**

Thx alot. I tested my program and here's the bug. I used int for my bigmod function, but turns out that it's not enough. I just used long long and everything worked just fine. Now I got AC.

### Re: 10006 - Carmichael Numbers

Posted: **Mon Feb 23, 2009 11:47 pm**

by **blackSajia**

Worng ans again again. Plzzzz help me . I give the 15 carmichael number of bellow 65000. these are

561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973.

My program give the right ans.but i get wa in uva. pls help

Code: Select all

```
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAX 65005
char a[MAX]={0};
int fact[100];
void prime();
bool isprime(int n);
bool iscarmichael(int n);
int buildPrimeFactor(int n)
{
int i,j;
for(i=1,j=0;i<=n;i++)
if(!(n%i)&&isprime(i))
fact[j++]=i,n/=i,i=1;
return j-1;
}
int main()
{
int n;
prime();
while(1)
{
scanf("%d",&n);
if(n==0)
break;
if(isprime(n))
printf("%d is normal.\n",n);
else
{
if(n%2)
{
if(iscarmichael(n))
printf("The number %d is a Carmichael number.\n",n);
else
printf("%d is normal.\n",n);
}
else
printf("%d is normal.\n",n);
}
}
return 0;
}
void prime()
{
int i,j,sq;
for(i=4;i<MAX;i+=2)
a[i]=1;
sq=(int)sqrt(MAX);
for(i=3;i<=sq;i+=2)
for(j=i+i;j<MAX;j+=i)
a[j]=1;
}
bool isprime(int n)
{
if(a[n]==0)
return true;
return false;
}
bool iscarmichael(int n)
{
int numFactor=buildPrimeFactor(n),i;
bool flag=true;
if(numFactor<3)
flag= false;
else
for(i=0;i<numFactor;i++)
if(i!=numFactor-1&&fact[i]==fact[i+1])
flag= false;
return flag;
}
```

### Re: 10006 - Carmichael Numbers

Posted: **Mon Feb 23, 2009 11:58 pm**

by **mf**

Really? Did you even test your program? I think, no:

ivank@zoidberg:~/contest$ xsel -b >p.cc # - this pastes your code into file p.cc

ivank@zoidberg:~/contest$ g++ -O2 -o p p.cc

ivank@zoidberg:~/contest$ seq 1 65000 | ./p | grep Carmichael | head

The number 75 is a Carmichael number.

The number 105 is a Carmichael number.

The number 147 is a Carmichael number.

The number 165 is a Carmichael number.

The number 195 is a Carmichael number.

The number 231 is a Carmichael number.

The number 245 is a Carmichael number.

The number 255 is a Carmichael number.

The number 273 is a Carmichael number.

The number 285 is a Carmichael number.

ivank@zoidberg:~/contest$

### Re: 10006 - Carmichael Numbers

Posted: **Sat Feb 28, 2009 9:11 pm**

by **blackSajia**

### 10006 - Carmichael Numbers

Posted: **Tue Jun 09, 2009 8:02 pm**

by **dipal**

Hi,

i accepted this pro 0.036s using find a num carmichael or not;

but when i precalculate these and output at O(1) time then i got 0.028 s.

if u chk the statistics of it then u find 0.000 .008 0.012 and .....

but how this is possible ??

Please some one explain it.

Its a Mystery to me...

thnx

### Re: 10006 - Carmichael Numbers

Posted: **Wed Jun 10, 2009 10:53 pm**

by **mf**

Please don't abbreviate English words, it's just rude!

When computational time in a problem is insignificant, you shouldn't forget about I/O time. scanf/printf is faster that C++'s iostream. And custom-made input/output routines, directly talking to the OS (for example, via mmap()) can be faster than scanf/printf.

### Re: 10006 - Carmichael Numbers

Posted: **Mon Jun 15, 2009 8:53 am**

by **dipal**

Please don't abbreviate English words, it's just rude!

sorry for it.

actually i used scanf/printf .

thnx for reply.

### 10006 WA. Help Me!

Posted: **Mon Sep 03, 2012 2:20 am**

by **cse.mehedi**

Code: Select all

```
#include<stdio.h>
#include<math.h>
#define M 80000
char prime[M];
int main()
{
long n,i,c,l,flag;
sieve();
while(1)
{
scanf("%ld",&n); if(n==0) break;
printf("AC");
}
return 0;
}
```

### Re: 10006 WA. Help Me!

Posted: **Wed Sep 05, 2012 1:51 am**

by **brianfry713**

30 is normal.

### Re: 10006 WA. Help Me!

Posted: **Fri Sep 07, 2012 7:10 pm**

by **cse.mehedi**

brianfry713 wrote:30 is normal.

i changed but again WA!