10006 - Carmichael Numbers

[M.Z]

I got wrong answer. Anyone can help me about this!
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]

Change "int" to "unsigned", and you'll get it.
There're 15 numbers totally instead of 11.

[oracle]

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]

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]

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]

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]

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]

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.

[WanBa]

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

[carneiro]

That's a good question for Revilla

[nikhil]

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
help me please...

#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]

is there a way to solve this problem without precalculate ?

[shamim]

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]

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.

[Farid Ahmadov]

Hey people. Don't you know that a*a when a>sqrt(maxlongint) causes overflow with int????