## 10006 - Carmichael Numbers

Moderator: Board moderators

M.Z
New poster
Posts: 3
Joined: Sat Jul 20, 2002 4:48 am

### 10006 - Carmichael Numbers

Thank you very much!

Code: Select all

``````[cpp]
/*

#include<iostream.h>

#include<fstream.h>
ofstream out("es_10006.out");

int notprime[65000];
int prime[6505];
int num[100];

int cal(int a,int k,int n)
//return a^k(mod n)
{
int ans=a;
if(k==1) return a;
if(k%2){
return (a*cal((a*a)%n,k/2,n))%n;
}else{
return cal((a*a)%n,k/2,n);
}
}

void main()
{
int tot;
int i,j;
for(i=1;i<65000;i++) notprime[i]=0;
prime[0]=2;
tot=1;
for(i=3;i<65000;i+=2){
if(!notprime[i]){
prime[tot++]=i;
for(j=3;j<=65000/i;j+=2){
notprime[i*j]=1;
}
}
}

int n,a;
tot=0;
for(n=3;n<65000;n++){
if(!notprime[n]) continue;
for(a=2;a<n;a++){
if(cal(a,n,n)!=a) break;
}
if(a==n) num[tot++]=n;
}

out<<tot<<endl;
for(i=0;i<tot;i++){
out<<num[i]<<endl;
}
}

*/

#include<iostream.h>
int num[11]={561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041};
void main()
{
int n;
int i;
while(1){
cin>>n;
if(!n) break;
for(i=0;i<11;i++) if(num[i]==n) break;
if(i==11) cout<<n<<" is normal."<<endl;
else cout<<"The number "<<n<<" is a Carmichael number."<<endl;
}
}
[/cpp]``````

DailyByte
New poster
Posts: 4
Joined: Sat Jul 20, 2002 12:54 pm
Change "int" to "unsigned", and you'll get it.
There're 15 numbers totally instead of 11.

oracle
New poster
Posts: 4
Joined: Tue Sep 17, 2002 6:21 pm
I've already found out 15 Carmichael numbers which are <65000

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

But my program stil getl wrong answer. Can you check for me if above numbers are correct ?[/cpp]

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
yes, it's correct.
about WA, i'm not really sure, but _i think_ there may be more than one number in a single line, lot of leading blanks, and so on. Maybe you could try that.

Code: Select all

``````     20934                 234           21
19238                                             1203

123            21903                                               6601
10585

313         41          5            52633
0
``````

oracle
New poster
Posts: 4
Joined: Tue Sep 17, 2002 6:21 pm
Thank you to help me to concentrate on other part. I finnaly found out the problems, it's when I send problem using Yahoo Mail, it cut down the long line which contain 'printf()', so the output format have been changed unknowingly.

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### MILLION THANKS

THANKS SO MUCH to the person who suggested using unsigned instead of int. My previous program got WA and used as much as 9seconds. After changing all int to unsigned, it got ACCEPTED and even finished with 1.6 seconds, which is still slow compared to other authors' submissions. But this unsigned thingy is exactly the kind of killer bug for me...I swear I would never think the int is the problem. Many thanks again.

beska
New poster
Posts: 2
Joined: Thu Mar 13, 2003 2:10 am
Ok...I've given up on this. What on earth is going on with this problem? I wrote the program, and got it to run on my machine, but whenever I submitted it it timed out. I eventually got to the point where, after optimizing until the cows came home, wondered if I was even getting the right answer...so I just wrote a short program that just hard codes the few Carmichael numbers in, and prints out the appropate string. When I submitted it, it passed...after 2.5+ CPU seconds! That's 1/4 of the time right there with basically *no* computation. How on earth do people manage to get this to run in 10 CPU seconds, when a program with no computation takes 1/4 of the time by itself?

FlareCDE
New poster
Posts: 3
Joined: Fri Mar 21, 2003 6:31 pm
Location: New York
Contact:
What language are you using? I have heard of a lot of people having problems with Java, even hard coding it (cheating :) ). I used C++ and it was a lot swifter.

And thanks to this thread I finally got it, dunno why I didn't think of changing all my ints to unsigned in the first place.
- Flare Araxion

WanBa
New poster
Posts: 14
Joined: Mon Apr 28, 2003 11:21 am
can anyone tell me why there is a bug when using " int ",and how it is dissipated by superseding with " unsigned" ??

best regards angone lend me hand
destiny conditioned by past

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
That's a good question for Revilla
[]s
Mauricio Oliveira Carneiro

nikhil
New poster
Posts: 11
Joined: Wed Oct 08, 2003 1:37 pm

i got this ac
but before i had to generate the car numbers
is there any better procedure???????????????
there are 2 extra numbers at the end of the array before 0

#include<stdio.h>

long a,ar[]={561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973,75361,0};

int main(void){
int x, found;

while(1==scanf("%ld", &a) && a){
for(found=x=0;ar[x];x++)
if(a==ar[x]){
printf("The number %ld is a Carmichael number.\n", a);
found=1;
break;
}
if(!found)
printf("%ld is normal.\n", a);
}
return 0;
}

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

### 10006 Time Limit Exceeded

is there a way to solve this problem without precalculate ?

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
I guess so, because even by submitting precalulateed result, I could not solve it in 0 seconds, infact no one has done so yet.

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am
but i've test in my comp (Celeron 1,1 GHZ), it's only take 2 second to find all carmichael number < 65000, but when i submitted itu (only the function to find carmichael number) i got TLE.