Page 1 of 3
Re: 10924 - Prime Words
Posted: Sun Oct 02, 2005 1:08 am
"A prime number is a number that has only two divisors: itself and the number one. Examples of prime numbers are: 1, ..."
That statement is contradictory.
Not at all!
According to the definition given above 1 is a prime number.
Number 1 does not have *two* divisors! Therefore 1 is not a prime number!
If you are going to count divisors more than once then every number has infinite divisors!
1 has only two divisors (1 and itself).
Posted: Sun Oct 02, 2005 2:05 am
Posted: Mon Oct 03, 2005 5:53 am
I didn't consider 1 as a input (even i didn't read the problem totally) and got Acc. Then after watching this post, I opened my code and see that my BANGLA TYPE prime finding algo is covering one as a PRIME !!!.
int isPrime(int num)
if(num == 2 || num == 3 || num == 5)
I never wrote this function so carelessly, but this was the first time I took a prime finding problem so carelessly and just write this BANGLA Type algo! And it saved me !!! ha ha ha.
But 1 is not prime, as a prime must have two divisor at least and 1 and 1 can not be considered as two different divisor.
Posted: Mon Oct 03, 2005 5:55 am
The number 1 is a special case which is considered neither prime nor composite (Wells 1986, p. 31). Although the number 1 used to be considered a prime (Goldbach 1742; Lehmer 1909; Lehmer 1914; Hardy and Wright 1979, p. 11; Gardner 1984, pp. 86-87; Sloane and Plouffe 1995, p. 33; Hardy 1999, p. 46), it requires special treatment in so many definitions and applications involving primes greater than or equal to 2 that it is usually placed into a class of its own. A good reason not to call 1 a prime number is that if 1 were prime, then the statement of the fundamental theorem of arithmetic would have to be modified since "in exactly one way" would be false because any n==n.1. In other words, unique factorization into a product of primes would fail if the primes included 1. A slightly less illuminating but mathematically correct reason is noted by Tietze (1965, p. 2), who states "Why is the number 1 made an exception? This is a problem that schoolboys often argue about, but since it is a question of definition, it is not arguable." As more simply noted by Derbyshire (2004, p. 33), "2 pays its way [as a prime] on balance; 1 doesn't."
With 1 excluded, the smallest prime is therefore 2. However, since 2 is the only even prime (which, ironically, in some sense makes it the "oddest" prime), it is also somewhat special, and the set of all primes excluding 2 is therefore called the "odd primes." Note also that while 2 is considered a prime today, at one time it was not (Tietze 1965, p. 18; Tropfke 1921, p. 96).
Re: 10924 - Prime Words
Posted: Mon Oct 03, 2005 10:32 am
kp wrote:1 has only two divisors (1 and itself).
Oh you're right, how could I be so blind?
1 has two divisors, 1 and 1!
I knew that 1 was a divisor but I forgot about 1!
Wait a minute! Actually 1 has three divisors: 1, 1 and 1. Or maybe five divisors, namely 1, 1, 1, 1, and, of course, 1.
1 has two divisors 1 and "itself"
"itself" here is not a common number it's just itself
You say that 1 has three divisors 1, 1 and 1 but you just
count one divisor "1" for three times!
The problem statement may contain such definition:
"Let's call a number prime if it is odd".
So in this problem primes are 1, 3, 5, ...
All I want to say that definition cannot be wrong!
Count 1 as a prime number or not is a matter of taste.
Posted: Mon Oct 03, 2005 8:08 pm
i always consider 1 as non prime, and in my sieve function i always put the position 1 and 0 marked at 1st place because once i was caught for not doing so in a problem. and my solution which considers 1 as nonprime got accepted in contest ( i fortunately missed that part ). so the judge data doesn't has '1' in input.
i think in programming world, 1 is considered as non prime. and if a problem defines it other way, some confusion arises. but if it is mentioned in the problem description that 1 is prime, than we should follow that for that perticular problem.
Posted: Mon Oct 03, 2005 9:10 pm
sorry, it is true that 1 was in the input. problem is that I checked my code again and found that i mistakenly marked 1 as prime (?).
Posted: Tue Oct 04, 2005 8:47 am
Jalal, u did the same thing that i did !
In the contest some time one WA can force a team to go down by 10/20 places. So, this thing has to be solved. If any problem setter takes 1 as prime, then he/she must put that information in the problem.
I hope, in future, all the problem setters will keep this fact in mind.
Posted: Wed Oct 05, 2005 3:40 pm
consider this input
output should be "It is a prime word.",
but your program outputs the other one.
limit = ceil( sqrt( n ) + 0.5 );
limit = floor( sqrt( n ) + 0.5 );
and you should get rid of the error.
Posted: Wed Aug 09, 2006 10:19 am
I too have have problems with this problem(WA). There are no test cases posted other than the ones on the problem, which my program outputs correctly. Can anyone give me test cases or find a problem in my code?
Code: Select all
using namespace std;
bool isprime(int n)
if(n==1) return 1;
if(n==2) return 1;
if(n%2==0) return 0;
if(n%i==0) return 0;
if(str1[i]>='A' && str1[i]<='Z')
else if(str1[i]>='a' && str1[i]<='z')
if(isprime(prime)) cout << "It is a prime word.\n";
else cout <<"It is not a prime word.\n";
Posted: Thu Aug 10, 2006 9:00 am
mhayter1 wrote:I too have have problems with this problem(WA). There are no test cases posted other than the ones on the problem, which my program outputs correctly. Can anyone give me test cases or find a problem in my code?
Your code looks fine and it worked on all test cases I've tried it on (about 3M random cases).
Posted: Sat Aug 12, 2006 3:32 am
Thank you for your reply. It is very strange. I just recompiled my code and submitted it and it was accepted. Why did it get WA in the first place?
Posted: Sat Aug 12, 2006 7:37 pm
mhayter1 wrote:Thank you for your reply. It is very strange. I just recompiled my code and submitted it and it was accepted. Why did it get WA in the first place?
After getting AC, please, remove the code from your previous post.
Posted: Wed Jun 27, 2007 7:23 pm
I have do the problem and I sure its ok.
But whats hell happen to online judge???
when i submit it, it show WA.
Any one can help?
Here my code-
Code: Select all
Code has removed after getting AC.
I think this type problem should not proceed in ACM bcoz, here, in this problem a wrong information is used. (1 is prime!!!
Posted: Thu Jun 28, 2007 5:19 am
See the previous posts.. (the first post)