Page 4 of 5

Re: 10006 - Carmichael Numbers

Posted: Tue Sep 09, 2008 7:32 am
by 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....

Re: 10006 - Carmichael Numbers

Posted: Wed Feb 11, 2009 2:22 pm
by 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!

Re: 10006 - Carmichael Numbers

Posted: Wed Feb 11, 2009 4:05 pm
by 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.

Re: 10006 - Carmichael Numbers

Posted: Wed Feb 11, 2009 11:30 pm
by 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.

Re: 10006 - Carmichael Numbers

Posted: Thu Feb 12, 2009 9:38 am
by 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

Re: 10006 - Carmichael Numbers

Posted: Thu Feb 12, 2009 5:55 pm
by 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.

Re: 10006 - Carmichael Numbers

Posted: Mon Feb 23, 2009 11:47 pm
by 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;
}




Re: 10006 - Carmichael Numbers

Posted: Mon Feb 23, 2009 11:58 pm
by 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$

Re: 10006 - Carmichael Numbers

Posted: Sat Feb 28, 2009 9:11 pm
by blackSajia
Thankssssssssss to mf. Finally got AC. :lol: :lol: :lol:

10006 - Carmichael Numbers

Posted: Tue Jun 09, 2009 8:02 pm
by 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

Re: 10006 - Carmichael Numbers

Posted: Wed Jun 10, 2009 10:53 pm
by 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.

Re: 10006 - Carmichael Numbers

Posted: Mon Jun 15, 2009 8:53 am
by dipal
Please don't abbreviate English words, it's just rude!

sorry for it.

actually i used scanf/printf .
thnx for reply.

10006 WA. Help Me!

Posted: Mon Sep 03, 2012 2:20 am
by 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;
    }




Re: 10006 WA. Help Me!

Posted: Wed Sep 05, 2012 1:51 am
by brianfry713
30 is normal.

Re: 10006 WA. Help Me!

Posted: Fri Sep 07, 2012 7:10 pm
by cse.mehedi
brianfry713 wrote:30 is normal.
i changed but again WA!