10924 - Prime Words

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Re: 10924 - Prime Words

Post by kp » 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).

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Oct 02, 2005 2:05 am


Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Post by Niaz » 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)
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.
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Post by Niaz » 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).
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Re: 10924 - Prime Words

Post by kp » Mon Oct 03, 2005 10:32 am

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.

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » 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.
Jalal : AIUB SPARKS

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » 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 (?). :x how funny....
Jalal : AIUB SPARKS

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Post by Niaz » 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.
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Wed Oct 05, 2005 3:40 pm

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.

mhayter1
New poster
Posts: 15
Joined: Wed Jul 26, 2006 10:00 am

Post by mhayter1 » 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

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

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » 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).

mhayter1
New poster
Posts: 15
Joined: Wed Jul 26, 2006 10:00 am

Post by mhayter1 » 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?
Thanks anyway!!

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » 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?
Thanks anyway!!
After getting AC, please, remove the code from your previous post.

kintu
New poster
Posts: 6
Joined: Sun Mar 18, 2007 11:31 am
Location: In home

why WA?????

Post by kintu » 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!!! :o )
Last edited by kintu on Thu Jun 28, 2007 9:53 am, edited 2 times in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Thu Jun 28, 2007 5:19 am

See the previous posts.. (the first post)

Post Reply

Return to “Volume 109 (10900-10999)”