Page 1 of 3

Re: 10924 - Prime Words

Posted: Sun Oct 02, 2005 1:08 am
by kp
"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
by Larry

Posted: Mon Oct 03, 2005 5:53 am
by Niaz
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)
return 1;
for(long i=2;i<=sqrt(double(num));i++)
{
if(num%i==0)
return 0;
}
return 1;
}

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
by Niaz
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
by kp
Anonymous wrote:
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.
Funny...


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!

P.S.
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
by CodeMaker
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
by CodeMaker
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 (?). :x how funny....

Posted: Tue Oct 04, 2005 8:47 am
by Niaz
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
by sohel
consider this input

Code: Select all

c
output should be "It is a prime word.",
but your program outputs the other one.

change

limit = ceil( sqrt( n ) + 0.5 );

to

limit = floor( sqrt( n ) + 0.5 );

and you should get rid of the error.

Posted: Wed Aug 09, 2006 10:19 am
by mhayter1
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

#include<iostream>
#include<string>
using namespace std;

bool isprime(int n)
{
    if(n==1) return 1;
    if(n==2) return 1;
    if(n%2==0) return 0;
    for(int i=3;i*i<=n;i+=2)
    {
        if(n%i==0) return 0;
    }
    return 1;
}

int main()
{
    string str1;
    int prime;
    while(cin>>str1)
    {
        prime=0;
        for(int i=0;i<str1.size();i++)
        {
            if(str1[i]>='A' && str1[i]<='Z')
            {
                prime+=(str1[i]-'A'+27);
            }
            else if(str1[i]>='a' && str1[i]<='z')
            {
                prime+=(str1[i]-'a'+1);
            }
        }
        if(isprime(prime)) cout << "It is a prime word.\n";
        else cout <<"It is not a prime word.\n";
    }
    return 0;
}

Posted: Thu Aug 10, 2006 9:00 am
by Martin Macko
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
by mhayter1
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?
Thanks anyway!!

Posted: Sat Aug 12, 2006 7:37 pm
by Martin Macko
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?
Thanks anyway!!
After getting AC, please, remove the code from your previous post.

why WA?????

Posted: Wed Jun 27, 2007 7:23 pm
by kintu
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!!! :o )

Posted: Thu Jun 28, 2007 5:19 am
by helloneo
See the previous posts.. (the first post)