10006  Carmichael Numbers
Moderator: Board moderators

 New poster
 Posts: 13
 Joined: Mon Sep 08, 2008 6:57 pm
 Location: State University of Bangladesh
Re: 10006  Carmichael Numbers
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....
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....
Never think too hard, let ideas come to you...

 New poster
 Posts: 26
 Joined: Fri Jan 02, 2009 12:41 am
Re: 10006  Carmichael Numbers
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!
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
Quote from problem statement:
17 is a prime.Some numbersthat are not prime still pass the Fermat test with every number smaller than themselves. These numbers are called Carmichael numbers.

 New poster
 Posts: 26
 Joined: Fri Jan 02, 2009 12:41 am
Re: 10006  Carmichael Numbers
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.
Code: Select all
Removed after AC!
Last edited by alirezanoori on Thu Feb 12, 2009 5:56 pm, edited 1 time in total.
Re: 10006  Carmichael Numbers
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
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

 New poster
 Posts: 26
 Joined: Fri Jan 02, 2009 12:41 am
Re: 10006  Carmichael Numbers
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.

 New poster
 Posts: 4
 Joined: Tue Nov 11, 2008 12:14 pm
Re: 10006  Carmichael Numbers
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
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 j1;
}
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!=numFactor1&&fact[i]==fact[i+1])
flag= false;
return flag;
}
Re: 10006  Carmichael Numbers
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$
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$

 New poster
 Posts: 4
 Joined: Tue Nov 11, 2008 12:14 pm
Re: 10006  Carmichael Numbers
Thankssssssssss to mf. Finally got AC.
10006  Carmichael Numbers
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
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
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 custommade input/output routines, directly talking to the OS (for example, via mmap()) can be faster than scanf/printf.
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 custommade input/output routines, directly talking to the OS (for example, via mmap()) can be faster than scanf/printf.
Re: 10006  Carmichael Numbers
Please don't abbreviate English words, it's just rude!
sorry for it.
actually i used scanf/printf .
thnx for reply.

 New poster
 Posts: 36
 Joined: Sun Mar 18, 2012 8:18 am
10006 WA. Help Me!
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;
}
Last edited by cse.mehedi on Fri Sep 07, 2012 8:08 pm, edited 2 times in total.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA

 New poster
 Posts: 36
 Joined: Sun Mar 18, 2012 8:18 am
Re: 10006 WA. Help Me!
i changed but again WA!brianfry713 wrote:30 is normal.