## 10006 - Carmichael Numbers

**Moderator:** Board moderators

### 10006-WA why

Is there anyone to help me.

code deleted.

although it outputs correctly judge says wrong answer.please help.

code deleted.

although it outputs correctly judge says wrong answer.please help.

Last edited by sohag144 on Sat Apr 15, 2006 2:19 pm, edited 1 time in total.

Shahadat Hossain Sohag

CSE-BUET-0405089

http://sites.google.com/site/sohagbuetcse/

http://acm.uva.es/problemset/usersjudge.php?user=4428

CSE-BUET-0405089

http://sites.google.com/site/sohagbuetcse/

http://acm.uva.es/problemset/usersjudge.php?user=4428

yeh.i found my bug , i have to use long long in bigmod() function.

Shahadat Hossain Sohag

CSE-BUET-0405089

http://sites.google.com/site/sohagbuetcse/

http://acm.uva.es/problemset/usersjudge.php?user=4428

CSE-BUET-0405089

http://sites.google.com/site/sohagbuetcse/

http://acm.uva.es/problemset/usersjudge.php?user=4428

### Only pre-calculating?

I solved this problem by precalculating the Carmichael Numbers and, from the topics above, I think this is the only to solve the problem without TLE. Am I right?

"Don't let the day go by

Don't let it end

Don't let the day go by, in doubts

The anwser lis within"

Don't let it end

Don't let the day go by, in doubts

The anwser lis within"

### Re: Plz Help me...

J&Jewel wrote:Here is my code I do not understand why this out Wrong Ans:..Plz Help me.....

#include<stdio.h>

int main()

{

int i;

long input,array[15]={561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973};

while(scanf("%ld",&input)==1)

{

if(input==0) break;

int k=0;

for(i=0;i<=14;i++)

{

if(input==array)

{

printf("The number %ld is a Charmichael number.\n",input);

k++;

break;

}

}

if(k==0) printf("%ld is normal.\n",input);

}

return 0;

}

The OJ says to print "The number 561 is a Carmichael number.".. while yours prints out "The number 561 is a Charmichael number"..

The OJ says to print "The number 561 is a Carmichael number.".. while yours prints out "The number 561 is a Charmichael number"..

### help! I dont understand why I get TLE

My computer runs my code so quickly, and gets all of the answers right, but it still gets TLE. I have taken all the advice I could from the boards and even took into account the possibility of entering a value that is not an integer. I am getting pretty frustrated seeing TLE so much.

When I try to pre-generate, my computer freezes. Please help!

Code: Select all

```
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
//adapted from prime_factorization()
bool isPrime(unsigned long x)
{
unsigned long i; /* counter */
unsigned long c; /* remaining product to factor */
c = x;
while ((c % 2) == 0) {
//printf("%ld\n",2);
c = c / 2;
}
i = 3;
while (i <= (sqrt((double)c)+1)) {
if ((c % i) == 0) {
//printf("%ld\n",i);
c = c / i;
}
else
i = i + 2;
}
if (c > 1) return (c == x);
return 0;
}
//calculates a^n(mod n)
unsigned long fermat(unsigned long a,unsigned long totheN,unsigned long modN) {
if (totheN==0)
return 1;
else if (totheN==1)
return a%modN;
else if (totheN%2==0)
return (fermat(a,totheN/2,modN)*fermat(a,totheN/2,modN))%modN;
else
return ((a%modN)*(fermat(a,totheN-1,modN)%modN))%modN;
}
bool carmnumber(unsigned long n)
{
for(unsigned int i = 2; i < n; i++)
{
if(i == fermat(i,n,n))
{
if(isPrime(n)) { return 0; break; }
return 1;
break;
}
else
{ return 0;
break;
}
}
}
int main()
{
double n;
cin >> n;
while(n != 0)
{
if((n-(int)n) > 0) { cout << n << " is normal.\n"; }
else {
if(carmnumber((unsigned long)n)) { cout << "The number " << n << " is a Carmichael number.\n"; }
else { cout << n << " is normal.\n"; }
}
cin >> n;
}
}
```

### Precalculating

Well, precalculating really can take several seconds or even minutes, depending on what platform you use. So, what you can do is run a program that calculate this numbers and another program that returns this number instantly, using a switch case structure.Can someone give me a hint as to how to precalculate. I tried to precalculate by running through all the numbers from 2 to 65000 and putting it into an array if it was a carmichael number, but this wound up taking sooo much time.

I coudn't imagine another way to solve the problem.

Good luck!

"Don't let the day go by

Don't let it end

Don't let the day go by, in doubts

The anwser lis within"

Don't let it end

Don't let the day go by, in doubts

The anwser lis within"

- newton
- Experienced poster
**Posts:**162**Joined:**Thu Jul 13, 2006 7:07 am**Location:**Campus Area. Dhaka.Bangladesh-
**Contact:**

going to the link

http://www.comp.nus.edu.sg/~stevenha/pr ... l%20Number

i came to know that the number has exactly 3 or greater prime factor;

but i am confused that why 30 is not a carmaichel number?

30 = (3*5*2);

i know there is a wrong with me. but what is that?

may anyone explaine it?

newton............ simply the best

http://www.comp.nus.edu.sg/~stevenha/pr ... l%20Number

i came to know that the number has exactly 3 or greater prime factor;

but i am confused that why 30 is not a carmaichel number?

30 = (3*5*2);

i know there is a wrong with me. but what is that?

may anyone explaine it?

newton............ simply the best

I think this link would be enough to answer your question.

http://mathworld.wolfram.com/CarmichaelNumber.html

- newton
- Experienced poster
**Posts:**162**Joined:**Thu Jul 13, 2006 7:07 am**Location:**Campus Area. Dhaka.Bangladesh-
**Contact:**

Code: Select all

```
resolved after AC
```

NEWTON...................... SIMPLY THE BEST!

Last edited by newton on Sat Feb 10, 2007 1:40 pm, edited 2 times in total.

Oh, my god. I just found the silliest bug of my life. I was printing

instead of1729 is a Carmichael number.

Almost lost my head trying to find where the WA was...The number1729 is a Carmichael number.

Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

http://www.dreamviews.com

**Are you dreaming right now?**http://www.dreamviews.com

### Re: 10006 - Carmichael Numbers

i m getting wrong answer in this problem.

it seems to work correctly for all inputs including the 15 carmichael numbers in the range specified.

could anyone plz help me?

my code follows:

#include<iostream>

#include<cmath>

using namespace std;

int isprime(long n)

{ int i;

if(n==1||n==2)

return 0;

for(i=3;i<=(int)sqrt(n)+1;i+=2)

{

if(n%i==0)

return 0;

}

return 1;

}

int expm(long n)

{ unsigned long x,y,m,j;

for( j=2;j<n-1&&!isprime(j);j++)

{

x=1;

y=j;

m=n;

while( m>0)

{

if(m%2==1)

x=((x%n)*(y%n))%n;

y=((y%n)*(y%n))%n;

m/=2;

}

if(x%n!=j)

return 0;

}

return 1;

}

main()

{

unsigned long n;

while(1)

{

cin>>n;

if(n==0)

break;

if(isprime(n)==0&&expm(n)==1)

cout<<"The number "<<n<<" is a Carmichael number."<<endl;

else

cout<<n<<" is normal."<<endl;

}

return 0;

}

help me plz.

it seems to work correctly for all inputs including the 15 carmichael numbers in the range specified.

could anyone plz help me?

my code follows:

#include<iostream>

#include<cmath>

using namespace std;

int isprime(long n)

{ int i;

if(n==1||n==2)

return 0;

for(i=3;i<=(int)sqrt(n)+1;i+=2)

{

if(n%i==0)

return 0;

}

return 1;

}

int expm(long n)

{ unsigned long x,y,m,j;

for( j=2;j<n-1&&!isprime(j);j++)

{

x=1;

y=j;

m=n;

while( m>0)

{

if(m%2==1)

x=((x%n)*(y%n))%n;

y=((y%n)*(y%n))%n;

m/=2;

}

if(x%n!=j)

return 0;

}

return 1;

}

main()

{

unsigned long n;

while(1)

{

cin>>n;

if(n==0)

break;

if(isprime(n)==0&&expm(n)==1)

cout<<"The number "<<n<<" is a Carmichael number."<<endl;

else

cout<<n<<" is normal."<<endl;

}

return 0;

}

help me plz.