Page 4 of 5

### Re: 10006 - Carmichael Numbers

Posted: Tue Sep 09, 2008 7:32 am

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.

### Re: 10006 - Carmichael Numbers

Posted: Wed Feb 11, 2009 2:22 pm
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.

### Re: 10006 - Carmichael Numbers

Posted: Wed Feb 11, 2009 4:05 pm
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
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.

Code: Select all

``````Removed after AC!
``````
If there is ANYTHING wrong with it please let me know. Thanks.

### Re: 10006 - Carmichael Numbers

Posted: Thu Feb 12, 2009 9:38 am
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
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
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;

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
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
Thankssssssssss to mf. Finally got AC.   ### 10006 - Carmichael Numbers

Posted: Tue Jun 09, 2009 8:02 pm
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 ??

Its a Mystery to me...

thnx

### Re: 10006 - Carmichael Numbers

Posted: Wed Jun 10, 2009 10:53 pm
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
Please don't abbreviate English words, it's just rude!

sorry for it.

actually i used scanf/printf .

### 10006 WA. Help Me!

Posted: Mon Sep 03, 2012 2:20 am

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
30 is normal.

### Re: 10006 WA. Help Me!

Posted: Fri Sep 07, 2012 7:10 pm
brianfry713 wrote:30 is normal.
i changed but again WA!