[Tutor] prime numbers

[Ike Hall]

This actually would be a useful tool in this case.

and for the math-minded out there, the proof of it is VERY simple.  all this
simply states is that  of 2 numbers that multiply to give a value, one must
be less than or equal to (in the case that they are the same number) that
values square root, which is basically saying

of any 2 numbers that add to give a value, the smaller of the two must be
less than half of the output value.  This is the same thing, with a
different operation.

Thanks for pointing this out.  Very useful, especially in useless code :)

Ike
----- Original Message -----
From: "Timothy M. Brauch" <tbrauch@mindless.com>
To: <ahimsa@onetel.net.uk>; <tutor@python.org>
Sent: Monday, February 24, 2003 3:58 PM
Subject: Re: [Tutor] prime numbers


> >Hello folks
> >I am wanting to do an exercise that calls for a function to calculate
prime
> >numbers. I know that primes can *only* be divided by themself or by 1,
and
> >nothing else. My difficulty is translating this into parsimonious code
> >without labouriously working out all the possible prime numbers as
> conditions
> >for the if control.
> >So far I have attempted % and /, and various combinations, but after a
> while I
> >am almost including all the primes anyway. Can someone give me a nudge in
> the
> >right direction please.
> >Much appreciated
> >AmF
>
> I can think of one way to write short code to check if a number is prime.
> The smallest factor of a pair of factors must be less than or equal to the
> square root of the number.  I can't think of a clear way to say that.
Maybe
> a few examples...
>
> 4 --> (1,4) (2,2).  2 <= sqrt(4)
> 6 --> (1,6) (2,3).  2 <= sqrt(6)
> 8 --> (1,8) (2,4).  2 <= sqrt(8)
> 16 --> (1,16) (2,8) (4,4).  4 <= sqrt(16)
> 24 --> (1,24) (2,12) (3,8) (4,6) 4<= sqrt(24)
>
> A few more examples should be pretty convincing it is true.  If requested,
I
> could write up some sort of rigorous proof this is the case, but I am
tired
> after doing proofs all day long.  So, the short coding way to find if a
> number was prime or not would be to simply check it against all integers
> that are less than the square root of the number.
>
> However, just a little warning, this would only take a few lines of code,
> but it will be painfully slow as your numbers get bigger.  If you are just
> sticking with numbers say less than 100**2, then it probably won't take
too
> long to check 100 divisions.  Just remember, though, this code is far from
> efficient.  I guess you could write it so once it found one factor, to
stop;
> that should increase the efficiency, but it would also add a few lines to
> the code.
>
>  - Tim
>
>
> _______________________________________________
> Tutor maillist  -  Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor
>