10006 - Carmichael Numbers

[Moshiur Rahman]

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....

[alirezanoori]

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!

[mf]

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.

[alirezanoori]

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.

[mf]

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

[alirezanoori]

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.

[blackSajia]

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[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 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;
}

[mf]

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$

[blackSajia]

Thankssssssssss to mf. Finally got AC.

[dipal]

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

[mf]

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.

[dipal]

Please don't abbreviate English words, it's just rude!

sorry for it.

actually i used scanf/printf .
thnx for reply.

[cse.mehedi]

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;
    }

[brianfry713]

30 is normal.

[cse.mehedi]

30 is normal.

i changed but again WA!