Re: Prime testing [was Re: My backwards logic]
On Sun, Sep 7, 2014 at 11:53 AM, Peter Pearson wrote: > On Sat, 6 Sep 2014 12:53:16 +0200, Manolo Martínez wrote: >> On 09/06/14 at 08:38pm, Steven D'Aprano wrote: >>> But even that's not how the specialists do it. If you want to check whether >>> (say) 2**3000+1 is prime, you don't want to use trial division at all... >> >> When I was interested in these things, specialists would use the [number >> field sieve](https://en.wikipedia.org/wiki/General_number_field_sieve). > > No, one uses the number field sieve to *factor* large numbers. To > test for primality, one uses simple tests like Fermat's test (x**(n-1)%n == 1, > for many different x) or the slightly more complex Miller-Rabin test. Usually you'd preceed a Miller-Rabin test with trial division by some small primes, as division by small primes identifies a lot of composites more quickly than Miller-Rabin. > These probabilistic primality tests can prove that a number is composite, > but they can't actually *prove* that a number is prime. For that, you > need a more complex test that is beyond my ken as a cryptologist. Actually, smallish numbers are always correctly identified as prime or composite by Miller-Rabin. It's the big ones that aren't. For a deterministic primality test that works on large numbers, check out the AKS algorithm. -- https://mail.python.org/mailman/listinfo/python-list
Re: Prime testing [was Re: My backwards logic]
On 09/07/14 at 06:53pm, Peter Pearson wrote: > On Sat, 6 Sep 2014 12:53:16 +0200, Manolo Martínez wrote: > > On 09/06/14 at 08:38pm, Steven D'Aprano wrote: > >> But even that's not how the specialists do it. If you want to check whether > >> (say) 2**3000+1 is prime, you don't want to use trial division at all... > > > > When I was interested in these things, specialists would use the [number > > field sieve](https://en.wikipedia.org/wiki/General_number_field_sieve). > > No, one uses the number field sieve to *factor* large numbers. - Ugh. That's what I meant, of course :/ -- https://mail.python.org/mailman/listinfo/python-list
Re: Prime testing [was Re: My backwards logic]
On Sat, 6 Sep 2014 12:53:16 +0200, Manolo Martínez wrote: > On 09/06/14 at 08:38pm, Steven D'Aprano wrote: >> But even that's not how the specialists do it. If you want to check whether >> (say) 2**3000+1 is prime, you don't want to use trial division at all... > > When I was interested in these things, specialists would use the [number > field sieve](https://en.wikipedia.org/wiki/General_number_field_sieve). No, one uses the number field sieve to *factor* large numbers. To test for primality, one uses simple tests like Fermat's test (x**(n-1)%n == 1, for many different x) or the slightly more complex Miller-Rabin test. These probabilistic primality tests can prove that a number is composite, but they can't actually *prove* that a number is prime. For that, you need a more complex test that is beyond my ken as a cryptologist. -- To email me, substitute nowhere->runbox, invalid->com. -- https://mail.python.org/mailman/listinfo/python-list
Re: Prime testing [was Re: My backwards logic]
On 09/06/14 at 08:38pm, Steven D'Aprano wrote: > But even that's not how the specialists do it. If you want to check whether > (say) 2**3000+1 is prime, you don't want to use trial division at all... When I was interested in these things, specialists would use the [number field sieve](https://en.wikipedia.org/wiki/General_number_field_sieve). I coded a Mathematica implementation fifteen years ago or so. It was a lot of work :) Manolo -- https://mail.python.org/mailman/listinfo/python-list
Re: Prime testing [was Re: My backwards logic]
On Sat, Sep 6, 2014 at 8:38 PM, Steven D'Aprano wrote: > 3, 5, 7, 9 is a waste of time, 11, 13, 15 is a waste of time, ... I love this sequence. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Prime testing [was Re: My backwards logic]
Denis McMahon wrote: > Note also that when searching for factors of a number n, and starting at > 2, you can generally stop at somewhere around n/3, The largest factor of N you actually need to check is sqrt(n). Every factor of n below the square root has a corresponding factor above it, e.g. if n equals 100, then factor 2 (below 10) corresponds to factor 50 (above 10), so there's no need to test with numbers above the square root since you would have already detected their partner. (No need to check whether 50 is a factor, since you've already checked 2.) Stopping at n/2, or n/3, does a lot more work than necessary. E.g. for n equal to one million, we have: py> n = 10**6 py> n/2, n/3, n**0.5 (50.0, 33.33, 1000.0) Even there, we can improve matters by only dividing by primes: 3, 5, 7, 9 is a waste of time, 11, 13, 15 is a waste of time, ... If n is divisible by 9, it is also divisible by 3; likewise if n is divisible by 15, it is also divisible by both 3 and 5. There are only 78,498 primes below one million, compared to 499,999 odd numbers excluding 1, so if you can find away to only test against primes, you'll save a lot of time. But even that's not how the specialists do it. If you want to check whether (say) 2**3000+1 is prime, you don't want to use trial division at all... -- Steven -- https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On Fri, 05 Sep 2014 12:48:56 -0400, Seymore4Head wrote: > But, what this instructions want printed is "This is a prime number" > So how to I use this code logic NOT print (not prime) and have the logic > print "This number is prime" This is an algorithmic question, not a python question, so the answer is to write out the steps you would follow to determine that a number is prime, and then write that code. Note also that when searching for factors of a number n, and starting at 2, you can generally stop at somewhere around n/3, as the only possible factor of n greater than n/2 is n, and 2 is probably the first value you tested. This can speed things up. -- Denis McMahon, denismfmcma...@gmail.com -- https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
This is top posted and makes it extremely difficult to follow long threads with many replies. This is heavily frowned upon here. On 06/09/2014 02:54, Juan Christian wrote: @Mark Lawrence: Sorry to ask, but what do you mean by "don't top post here, thanks.", I'm not familiar with mailing lists, so I may be doing something wrong and I don't know. On Fri, Sep 5, 2014 at 4:54 PM, Mark Lawrence mailto:breamore...@yahoo.co.uk>> wrote: On 05/09/2014 20:34, Juan Christian wrote: What's [snip] ?? As in cut out or chopped out such that some of the original text has been removed. And please don't top post here, thanks. This is an interleaved reply that I'm putting here as an example. This is the preferred way of replying, especially on the longer threads. -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence -- This in bottom posted. Perfectly acceptable but usually only for the shorter messages. -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence -- https://mail.python.org/mailman/listinfo/python-list
Re: Posting style: interleaved responses (was: My backwards logic)
On Fri, Sep 5, 2014 at 10:06 PM, Juan Christian
wrote:
> On Fri, Sep 5, 2014 at 11:37 PM, Ben Finney
> wrote:
>>
>> Juan Christian writes:
>>
>> > @Mark Lawrence: Sorry to ask, but what do you mean by "don't top post
>> > here, thanks.", I'm not familiar with mailing lists, so I may be doing
>> > something wrong and I don't know.
>>
>> Please post your responses interleaved with the quoted material to
>> which you're responding. See the article on “interleaved style”
>> https://en.wikipedia.org/wiki/Posting_style#Interleaved_style>. And
>> trim any quoted material to which you're not responding, so your message
>> only contains relevant material.
>>
>> --
>> \“Human reason is snatching everything to itself, leaving |
>> `\ nothing for faith.” —Bernard of Clairvaux, 1090–1153 CE |
>> _o__) |
>> Ben Finney
>>
>> --
>> https://mail.python.org/mailman/listinfo/python-list
>
>
> Like that?
Almost. I left your entire message intact up to this point so you can
see what you sent, though you may need to click the [...] to expand it
[1]. (Normally, I would edit out everything but the actual message
I'm replying to ("Like that?") and some context from Ben's message.)
> I'm using gmail so it automatically put the text in the [...]
> icon.
Gmail (which I also use) requires a little bit of extra effort to
abide by proper mailing list etiquette; in particular, you should
always expand the [...]-hidden text and edit out what you don't need
to send such as signatures and footers from the message you're
replying to. Then add your replies immediately after the text you're
actually responding to, like I've done with this paragraph and my
previous one. It's also best to choose "plain text mode" from the
little menu at lower-right (choose that before you actually edit the
message at all, though, or set it as the default. Changing it
mid-message causes havoc with the formatting).
It's at least a step up from a certain other Google interface to this
list, and I think I speak for everyone in saying "thank you for being
willing to learn proper etiquette" :)
--
Zach
[1] Or look here:
https://mail.python.org/pipermail/python-list/2014-September/678058.html
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
Seymore4Head Wrote in message: > On Fri, 05 Sep 2014 12:48:56 -0400, Seymore4Head > wrote: > > > If you start with the list [3,5,7] and step through the list of all > remaining odd numbers (step 2), and start appending numbers that won't > divide by numbers already appended in the list, that would seem like a > pretty efficient way to find all prime numbers. > > Yes, that's a well known optimization. In addition, you can stop once you reach the square root of the target. No point in dividing by the higher numbers in the list, since if the result comes out even, you'd have already exited the loop. -- DaveA -- https://mail.python.org/mailman/listinfo/python-list
Re: Posting style: interleaved responses (was: My backwards logic)
On Fri, Sep 5, 2014 at 11:37 PM, Ben Finney wrote: > Juan Christian writes: > > > @Mark Lawrence: Sorry to ask, but what do you mean by "don't top post > > here, thanks.", I'm not familiar with mailing lists, so I may be doing > > something wrong and I don't know. > > Please post your responses interleaved with the quoted material to > which you're responding. See the article on “interleaved style” > https://en.wikipedia.org/wiki/Posting_style#Interleaved_style>. And > trim any quoted material to which you're not responding, so your message > only contains relevant material. > > -- > \“Human reason is snatching everything to itself, leaving | > `\ nothing for faith.” —Bernard of Clairvaux, 1090–1153 CE | > _o__) | > Ben Finney > > -- > https://mail.python.org/mailman/listinfo/python-list Like that? I'm using gmail so it automatically put the text in the [...] icon. -- https://mail.python.org/mailman/listinfo/python-list
Posting style: interleaved responses (was: My backwards logic)
Juan Christian writes: > @Mark Lawrence: Sorry to ask, but what do you mean by "don't top post > here, thanks.", I'm not familiar with mailing lists, so I may be doing > something wrong and I don't know. Please post your responses interleaved with the quoted material to which you're responding. See the article on “interleaved style” https://en.wikipedia.org/wiki/Posting_style#Interleaved_style>. And trim any quoted material to which you're not responding, so your message only contains relevant material. -- \“Human reason is snatching everything to itself, leaving | `\ nothing for faith.” —Bernard of Clairvaux, 1090–1153 CE | _o__) | Ben Finney -- https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On Saturday, September 6, 2014 7:25:10 AM UTC+5:30, Juan Christian wrote: > @Mark Lawrence: Sorry to ask, but what do you mean by "don't top post here, > thanks.", I'm not familiar with mailing lists, so I may be doing something > wrong and I don't know. Maybe better to say use this http://en.wikipedia.org/wiki/Posting_style#Interleaved_style rather than to say dont use http://en.wikipedia.org/wiki/Posting_style#Top-posting Also read https://wiki.python.org/moin/GoogleGroupsPython -- https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
@Mark Lawrence: Sorry to ask, but what do you mean by "don't top post here, thanks.", I'm not familiar with mailing lists, so I may be doing something wrong and I don't know. On Fri, Sep 5, 2014 at 4:54 PM, Mark Lawrence wrote: > On 05/09/2014 20:34, Juan Christian wrote: > >> What's [snip] ?? >> >> > As in cut out or chopped out such that some of the original text has been > removed. And please don't top post here, thanks. > > -- > My fellow Pythonistas, ask not what our language can do for you, ask > what you can do for our language. > > Mark Lawrence > > -- > https://mail.python.org/mailman/listinfo/python-list > -- https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On Saturday, September 6, 2014 1:37:57 AM UTC+5:30, Paul Rubin wrote:
> Juan Christian writes:
> > I made this code just for fun and learning, it's working, but would
> > this be a good approach? Thanks. ...
> > ** ** for number in range(start, stop + 1):
> > ** ** ** ** divisors = [(number % x) for x in range(1, number + 1)]
> > ** ** ** ** ** ** print("{n} prime? {r}".format(n = number, r =
> > (divisors.count(0) == 2)))
> 1. Mathematically it's better to stop checking once you've gone past
> the square root of the number, since if n = p*q and is composite,
> then at least one of p,q will be <= sqrt(n).
> 2. As a program design matter, it's generally preferable for functions
> like this to not print the answer. They should just return a value, in
> this case a bool indicating whether the number is prime. That makes it
> easier to re-use the function, to wrap it in a unit test framework, etc.
> If you want to print the result, then call the function and have the
> caller print the returned value.
Hoo boy! And we come full circle
> 3. As a simple optimization, once you have checked that the number is
> not divisible by 2, you don't have to check for other even divisors.
> So just check for 2, then the odd numbers 3,5,7...
> This is a little bit fancy but I like to use itertools for these
> sorts of problems:
> from itertools import chain, takewhile, count
> def is_prime(n):
> if n < 2: return False
> candidates = chain([2], count(3,2))
> return all(n%d!=0 for d in takewhile(lambda d: d*d<=n, candidates))
Paul's suggestions without the fancy -- no sqrt stop, no generators, no
itertools
etc -- (all to be learnt at their time of course!)
First of all I make for myself a closed range
>>> def crange(a,b) : return range(a,b+1)
Check it
>>> crange(1,10)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Now for divisors of a number
>>> def divisors(n): return [fact for fact in crange(1,n) if n%fact == 0]
Check it
>>> divisors(4)
[1,2,4]
>>> divisors(7)
[1, 7]
So now a prime is a number n whose divisors are only 1 and n
>>> def is_prime(n): return divisors(n) == [1,n]
>>> is_prime(2)
True
>>> is_prime(3)
True
>>> is_prime(4)
False
>>> is_prime(5)
True
>>> is_prime(6)
False
>>> is_prime(7)
True
So collecting the code together
>>> def crange(a,b): return range(a,b+1)
>>> def divisors(n): return [fact for fact in crange(1,n) if n%fact == 0]
>>> def is_prime(n): return divisors(n) == [1,n]
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On Sat, Sep 6, 2014 at 3:44 AM, Seymore4Head wrote: > BTW since I am getting no grade, I much prefer the answer than a hint. > The best hint IMO is to tell me how you would do it. But for your own learning, it's still better for you to do things yourself. Giving you the answer doesn't teach you nearly as effectively as giving you a hint and having you work out the answer yourself. But telling you how we'd do it can be useful too, especially when we get down to the detaily bits where there are lots of ways to do things. For instance, there's been a suggestion made a few times to break the primality test out into a function... but compare these two: def isprime(n): """Return True iff n is prime""" def find_factor(n): """Return a factor of n, or None if n is prime""" Aside from inverting the truth value, these are both tests of primality - you can write "if isprime(n):" or "if find_factor(n):" and they'll both work. (The latter is actually "iscomposite".) But the second function is giving you a bit more information - it tells you what factor it found. As a general rule, try to avoid throwing information away. To prove that n is composite, your function found a factor. Returning that, rather than a boolean value, might make your function more useful; and it's zero cost, because you know that factors of a number will never be zero. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On Fri, 5 Sep 2014 16:35:18 -0600, Ian Kelly wrote: >On Fri, Sep 5, 2014 at 3:49 PM, Seymore4Head > wrote: >> I am sure this has already been done, but after it was pointed out >> that you don't need to test for any number that multiplies by 2 it >> made me think again. >> >> If you start with the list [3,5,7] and step through the list of all >> remaining odd numbers (step 2), and start appending numbers that won't >> divide by numbers already appended in the list, that would seem like a >> pretty efficient way to find all prime numbers. > >Indeed, this type of algorithm is known as a sieve. For a (literally) >classical example, see >http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes > >It's a nice way to find all the prime numbers up to a given limit, or >it can be modified to run indefinitely high, but it's not very >efficient for determining the primality of a single number. That is a pretty nice example. Thanks -- https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On Fri, 5 Sep 2014 15:14:41 -0700, Chris Kaynor
wrote:
>On Fri, Sep 5, 2014 at 2:49 PM, Seymore4Head
>wrote:
>
>> On Fri, 05 Sep 2014 12:48:56 -0400, Seymore4Head
>> wrote:
>>
>> >I'm still doing practice problems. I haven't heard from the library
>> >on any of the books I have requested.
>> >
>> >
>> http://www.practicepython.org/exercise/2014/04/16/11-check-primality-functions.html
>> >
>> >This is not a hard problem, but it got me to thinking a little. A
>> >prime number will divide by one and itself. When setting up this
>> >loop, if I start at 2 instead of 1, that automatically excludes one of
>> >the factors. Then, by default, Python goes "to" the chosen count and
>> >not "through" the count, so just the syntax causes Python to rule out
>> >the other factor (the number itself).
>> >
>> >So this works:
>> >while True:
>> >a=random.randrange(1,8)
>> >print (a)
>> >for x in range(2,a):
>> >if a%x==0:
>> >print ("Number is not prime")
>> >break
>> >wait = input (" "*40 + "Wait")
>> >
>> >But, what this instructions want printed is "This is a prime number"
>> >So how to I use this code logic NOT print (not prime) and have the
>> >logic print "This number is prime"
>>
>> I am sure this has already been done, but after it was pointed out
>> that you don't need to test for any number that multiplies by 2 it
>> made me think again.
>>
>> If you start with the list [3,5,7] and step through the list of all
>> remaining odd numbers (step 2), and start appending numbers that won't
>> divide by numbers already appended in the list, that would seem like a
>> pretty efficient way to find all prime numbers.
>>
>
>To be correct, you only need to check for n being divisible by primes less
>than sqrt(n). For example, the following code will produce a list of primes
>from 2 to 1000 (the result will be in the "primes" list):
>
>import math
>primes = [2]
>for i in range(3, 1000):
>end = math.sqrt(i)
>for x in primes:
>if x > end: # Once x is larger than the sqrt(i), we know it must be
>prime, so we can early exit.
>#print(i, "is a prime number")
>primes.append(i)
>break
>if (i % x) == 0:
>#print(i, "is a composite number")
>break
Thanks
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On Fri, Sep 5, 2014 at 3:49 PM, Seymore4Head wrote: > I am sure this has already been done, but after it was pointed out > that you don't need to test for any number that multiplies by 2 it > made me think again. > > If you start with the list [3,5,7] and step through the list of all > remaining odd numbers (step 2), and start appending numbers that won't > divide by numbers already appended in the list, that would seem like a > pretty efficient way to find all prime numbers. Indeed, this type of algorithm is known as a sieve. For a (literally) classical example, see http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes It's a nice way to find all the prime numbers up to a given limit, or it can be modified to run indefinitely high, but it's not very efficient for determining the primality of a single number. -- https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On Fri, Sep 5, 2014 at 2:49 PM, Seymore4Head
wrote:
> On Fri, 05 Sep 2014 12:48:56 -0400, Seymore4Head
> wrote:
>
> >I'm still doing practice problems. I haven't heard from the library
> >on any of the books I have requested.
> >
> >
> http://www.practicepython.org/exercise/2014/04/16/11-check-primality-functions.html
> >
> >This is not a hard problem, but it got me to thinking a little. A
> >prime number will divide by one and itself. When setting up this
> >loop, if I start at 2 instead of 1, that automatically excludes one of
> >the factors. Then, by default, Python goes "to" the chosen count and
> >not "through" the count, so just the syntax causes Python to rule out
> >the other factor (the number itself).
> >
> >So this works:
> >while True:
> >a=random.randrange(1,8)
> >print (a)
> >for x in range(2,a):
> >if a%x==0:
> >print ("Number is not prime")
> >break
> >wait = input (" "*40 + "Wait")
> >
> >But, what this instructions want printed is "This is a prime number"
> >So how to I use this code logic NOT print (not prime) and have the
> >logic print "This number is prime"
>
> I am sure this has already been done, but after it was pointed out
> that you don't need to test for any number that multiplies by 2 it
> made me think again.
>
> If you start with the list [3,5,7] and step through the list of all
> remaining odd numbers (step 2), and start appending numbers that won't
> divide by numbers already appended in the list, that would seem like a
> pretty efficient way to find all prime numbers.
>
To be correct, you only need to check for n being divisible by primes less
than sqrt(n). For example, the following code will produce a list of primes
from 2 to 1000 (the result will be in the "primes" list):
import math
primes = [2]
for i in range(3, 1000):
end = math.sqrt(i)
for x in primes:
if x > end: # Once x is larger than the sqrt(i), we know it must be
prime, so we can early exit.
#print(i, "is a prime number")
primes.append(i)
break
if (i % x) == 0:
#print(i, "is a composite number")
break
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On Fri, 05 Sep 2014 12:48:56 -0400, Seymore4Head
wrote:
>I'm still doing practice problems. I haven't heard from the library
>on any of the books I have requested.
>
>http://www.practicepython.org/exercise/2014/04/16/11-check-primality-functions.html
>
>This is not a hard problem, but it got me to thinking a little. A
>prime number will divide by one and itself. When setting up this
>loop, if I start at 2 instead of 1, that automatically excludes one of
>the factors. Then, by default, Python goes "to" the chosen count and
>not "through" the count, so just the syntax causes Python to rule out
>the other factor (the number itself).
>
>So this works:
>while True:
>a=random.randrange(1,8)
>print (a)
>for x in range(2,a):
>if a%x==0:
>print ("Number is not prime")
>break
>wait = input (" "*40 + "Wait")
>
>But, what this instructions want printed is "This is a prime number"
>So how to I use this code logic NOT print (not prime) and have the
>logic print "This number is prime"
I am sure this has already been done, but after it was pointed out
that you don't need to test for any number that multiplies by 2 it
made me think again.
If you start with the list [3,5,7] and step through the list of all
remaining odd numbers (step 2), and start appending numbers that won't
divide by numbers already appended in the list, that would seem like a
pretty efficient way to find all prime numbers.
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On Fri, Sep 5, 2014 at 11:44 AM, Seymore4Head
wrote:
> BTW since I am getting no grade, I much prefer the answer than a hint.
> The best hint IMO is to tell me how you would do it.
from math import ceil, sqrt
def is_prime(n):
if n < 2:
return False
if n % 2 == 0:
return n == 2
return all(n % x != 0 for x in range(3, int(sqrt(n)) + 1, 2))
while True:
n = int(input("Enter a number: "))
if is_prime(n):
print("{} is prime.".format(n))
else:
print("{} is not prime.".format(n))
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
Juan Christian writes:
> I made this code just for fun and learning, it's working, but would
> this be a good approach? Thanks. ...
> ** ** for number in range(start, stop + 1):
> ** ** ** ** divisors = [(number % x) for x in range(1, number + 1)]
> ** ** ** ** ** ** print("{n} prime? {r}".format(n = number, r =
> (divisors.count(0) == 2)))
1. Mathematically it's better to stop checking once you've gone past
the square root of the number, since if n = p*q and is composite,
then at least one of p,q will be <= sqrt(n).
2. As a program design matter, it's generally preferable for functions
like this to not print the answer. They should just return a value, in
this case a bool indicating whether the number is prime. That makes it
easier to re-use the function, to wrap it in a unit test framework, etc.
If you want to print the result, then call the function and have the
caller print the returned value.
3. As a simple optimization, once you have checked that the number is
not divisible by 2, you don't have to check for other even divisors.
So just check for 2, then the odd numbers 3,5,7...
This is a little bit fancy but I like to use itertools for these
sorts of problems:
from itertools import chain, takewhile, count
def is_prime(n):
if n < 2: return False
candidates = chain([2], count(3,2))
return all(n%d!=0 for d in takewhile(lambda d: d*d<=n, candidates))
If you're not familiar with those functions, "chain" concatenates
two sequences, and "count(n,i)" gives an increasing sequence starting
with n and incrementing by i. So chain([2], count(3,2)) gives
the unending sequence [2, 3, 5, 7, 9, ...] which is the numbers
you want to check against. Then the takewhile expression chops
that sequence once it gets past sqrt(n), and "all" returns true iff
all of the candidate divisors fail to divide the number.
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On 05/09/2014 20:34, Juan Christian wrote: What's [snip] ?? As in cut out or chopped out such that some of the original text has been removed. And please don't top post here, thanks. -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence -- https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
What's [snip] ??
On Fri, Sep 5, 2014 at 3:48 PM, MRAB wrote:
> On 2014-09-05 18:35, Juan Christian wrote:
>
>> I made this code just for fun and learning, it's working, but would this
>> be a good approach? Thanks.
>>
>> import sys
>>
>>
>> def prime_checker(start = 1, stop = 1):
>>
>
> In Python, the standard is to use a half-open range.
>
> for number in range(start, stop + 1):
>> divisors = [(number % x) for x in range(1, number + 1)]
>> print("{n} prime? {r}".format(n = number, r =
>> (divisors.count(0) == 2)))
>>
>> You want to know only whether it's prime, so why continue looking after
> finding a factor?
>
>>
>> if __name__ == '__main__':
>> prime_checker(int(sys.argv[1]), int(sys.argv[2]))
>>
>> [snip]
>
> --
> https://mail.python.org/mailman/listinfo/python-list
>
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On 2014-09-05 18:35, Juan Christian wrote:
I made this code just for fun and learning, it's working, but would this
be a good approach? Thanks.
import sys
def prime_checker(start = 1, stop = 1):
In Python, the standard is to use a half-open range.
for number in range(start, stop + 1):
divisors = [(number % x) for x in range(1, number + 1)]
print("{n} prime? {r}".format(n = number, r = (divisors.count(0) ==
2)))
You want to know only whether it's prime, so why continue looking after
finding a factor?
if __name__ == '__main__':
prime_checker(int(sys.argv[1]), int(sys.argv[2]))
[snip]
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On 09/05/2014 10:17 AM, Ian Kelly wrote: I would not worry about the else clause as a beginner, as it's relatively unique to Python and tends to be somewhat confusing. Use a flag or refactor the function instead. I don't disagree with this, but early exposure to "for..else is for search loops" is a good thing. I still get tripped up by this as I didn't learn it that way. -- ~Ethan~ -- https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On Fri, Sep 5, 2014 at 10:44 AM, Seymore4Head
wrote:
> On Fri, 05 Sep 2014 10:08:18 -0700, Ethan Furman
> wrote:
>
> >On 09/05/2014 09:48 AM, Seymore4Head wrote:
> >> I'm still doing practice problems. I haven't heard from the library
> >> on any of the books I have requested.
> >>
> >>
> http://www.practicepython.org/exercise/2014/04/16/11-check-primality-functions.html
> >>
> >> This is not a hard problem, but it got me to thinking a little. A
> >> prime number will divide by one and itself. When setting up this
> >> loop, if I start at 2 instead of 1, that automatically excludes one of
> >> the factors. Then, by default, Python goes "to" the chosen count and
> >> not "through" the count, so just the syntax causes Python to rule out
> >> the other factor (the number itself).
> >>
> >> So this works:
> >> while True:
> >> a=random.randrange(1,8)
> >> print (a)
> >> for x in range(2,a):
> >> if a%x==0:
> >> print ("Number is not prime")
> >> break
> >> wait = input (" "*40 + "Wait")
> >>
> >> But, what this instructions want printed is "This is a prime number"
> >> So how to I use this code logic NOT print (not prime) and have the
> >> logic print "This number is prime"
> >
> >Python's 'for' loop has a handy 'else' extension which is perfect for the
> search-type of 'for' loop:
> >
> >while True:
> > a=random.randrange(1,8)
> > print (a)
> > for x in range(2,a):
> > if a%x==0:
> > print ("Number is not prime")
> > break
> > else:
> > print ("Number is prime")
> > wait = input (" "*40 + "Wait")
> >
> >Note the two lines I added after the 'break' and before the 'wait'.
>
> I had already tried this one.
> The solution I want should only print:
> "This number is prime"
>
> Adding else causes the program to also print "This number is not
> prime"
>
If you do not want it to print the "Number is not prime", just remove the
print("Number is not prime") line.
> I also tried the flag=True suggestion, but never got one that worked.
> I am unsure when to use flag=True and flag==True
> Then there is flag="True" and flag=="True"
>
Generally, you would want to use:
flag = False
before the loop, and
flag = True
inside the loop (once you know the number is not prime). After the loop,
you would typically just use:
if flag: # This could be "if flag == True:", however the plain "if flag:"
is more Pythonic.
print("Number is prime")
The "=" operator is assignment - storing a new value.
The "==" operator is for equality checking. The inverse is the "!="
operator which checks for inequality.
What I really wanted was something like:
> if !(a%x==0)
In this case, that will not work, as you only know that the number is prime
after checking all the values, which means after the loop has completed.
Ignoring the fact that it would not function for this use case, the proper
Python syntax for that would be one of:
- if a%x != 0: # Probably the clearest for this case.
- if not (a%x==0):
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On Fri, 05 Sep 2014 10:08:18 -0700, Ethan Furman
wrote:
>On 09/05/2014 09:48 AM, Seymore4Head wrote:
>> I'm still doing practice problems. I haven't heard from the library
>> on any of the books I have requested.
>>
>> http://www.practicepython.org/exercise/2014/04/16/11-check-primality-functions.html
>>
>> This is not a hard problem, but it got me to thinking a little. A
>> prime number will divide by one and itself. When setting up this
>> loop, if I start at 2 instead of 1, that automatically excludes one of
>> the factors. Then, by default, Python goes "to" the chosen count and
>> not "through" the count, so just the syntax causes Python to rule out
>> the other factor (the number itself).
>>
>> So this works:
>> while True:
>> a=random.randrange(1,8)
>> print (a)
>> for x in range(2,a):
>> if a%x==0:
>> print ("Number is not prime")
>> break
>> wait = input (" "*40 + "Wait")
>>
>> But, what this instructions want printed is "This is a prime number"
>> So how to I use this code logic NOT print (not prime) and have the
>> logic print "This number is prime"
>
>Python's 'for' loop has a handy 'else' extension which is perfect for the
>search-type of 'for' loop:
>
>while True:
> a=random.randrange(1,8)
> print (a)
> for x in range(2,a):
> if a%x==0:
> print ("Number is not prime")
> break
> else:
> print ("Number is prime")
> wait = input (" "*40 + "Wait")
>
>Note the two lines I added after the 'break' and before the 'wait'.
I had already tried this one.
The solution I want should only print:
"This number is prime"
Adding else causes the program to also print "This number is not
prime"
I also tried the flag=True suggestion, but never got one that worked.
I am unsure when to use flag=True and flag==True
Then there is flag="True" and flag=="True"
What I really wanted was something like:
if !(a%x==0)
BTW since I am getting no grade, I much prefer the answer than a hint.
The best hint IMO is to tell me how you would do it.
Thanks everyone
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
I made this code just for fun and learning, it's working, but would this be
a good approach? Thanks.
import sys
def prime_checker(start = 1, stop = 1):
for number in range(start, stop + 1):
divisors = [(number % x) for x in range(1, number + 1)]
print("{n} prime? {r}".format(n = number, r = (divisors.count(0) == 2)))
if __name__ == '__main__':
prime_checker(int(sys.argv[1]), int(sys.argv[2]))
On Fri, Sep 5, 2014 at 2:17 PM, Ian Kelly wrote:
> On Fri, Sep 5, 2014 at 11:08 AM, Ethan Furman wrote:
> > Python's 'for' loop has a handy 'else' extension which is perfect for the
> > search-type of 'for' loop:
> >
> >while True:
> > a=random.randrange(1,8)
> > print (a)
> > for x in range(2,a):
> > if a%x==0:
> > print ("Number is not prime")
> > break
> > else:
> > print ("Number is prime")
> > wait = input (" "*40 + "Wait")
> >
> > Note the two lines I added after the 'break' and before the 'wait'.
>
> Also note that this construct tends to be particularly sensitive to
> indentation. If you accidentally indent the else block one level too
> many (which your editor may well do for you to "helpfully" match it up
> with the if), then you'll get a completely different result.
>
> I would not worry about the else clause as a beginner, as it's
> relatively unique to Python and tends to be somewhat confusing. Use a
> flag or refactor the function instead.
> --
> https://mail.python.org/mailman/listinfo/python-list
>
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On Fri, Sep 5, 2014 at 11:08 AM, Ethan Furman wrote:
> Python's 'for' loop has a handy 'else' extension which is perfect for the
> search-type of 'for' loop:
>
>while True:
> a=random.randrange(1,8)
> print (a)
> for x in range(2,a):
> if a%x==0:
> print ("Number is not prime")
> break
> else:
> print ("Number is prime")
> wait = input (" "*40 + "Wait")
>
> Note the two lines I added after the 'break' and before the 'wait'.
Also note that this construct tends to be particularly sensitive to
indentation. If you accidentally indent the else block one level too
many (which your editor may well do for you to "helpfully" match it up
with the if), then you'll get a completely different result.
I would not worry about the else clause as a beginner, as it's
relatively unique to Python and tends to be somewhat confusing. Use a
flag or refactor the function instead.
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
In <1enj0att6bkrnvb81rhma5dbuk3h28a...@4ax.com> Seymore4Head
writes:
> I'm still doing practice problems. I haven't heard from the library
> on any of the books I have requested.
> http://www.practicepython.org/exercise/2014/04/16/11-check-primality-functions.html
> This is not a hard problem, but it got me to thinking a little. A
> prime number will divide by one and itself. When setting up this
> loop, if I start at 2 instead of 1, that automatically excludes one of
> the factors. Then, by default, Python goes "to" the chosen count and
> not "through" the count, so just the syntax causes Python to rule out
> the other factor (the number itself).
> So this works:
> while True:
> a=random.randrange(1,8)
> print (a)
> for x in range(2,a):
> if a%x==0:
> print ("Number is not prime")
> break
> wait = input (" "*40 + "Wait")
> But, what this instructions want printed is "This is a prime number"
> So how to I use this code logic NOT print (not prime) and have the
> logic print "This number is prime"
There are two basic tactics you can use:
1. Initialize an "isprime" flag to True at the top of the while loop.
In the for loop, replace the print statement with a statement that
sets isprime to False. After the for loop, insert a check on isprime,
and print "This number is prime" if isprime is still True.
2. Create a separate function just for testing if a number is prime, which
returns True or False. Then call that function within your while loop.
--
John Gordon Imagine what it must be like for a real medical doctor to
gor...@panix.comwatch 'House', or a real serial killer to watch 'Dexter'.
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On Fri, Sep 5, 2014 at 9:48 AM, Seymore4Head
wrote:
> I'm still doing practice problems. I haven't heard from the library
> on any of the books I have requested.
>
>
> http://www.practicepython.org/exercise/2014/04/16/11-check-primality-functions.html
>
> This is not a hard problem, but it got me to thinking a little. A
> prime number will divide by one and itself. When setting up this
> loop, if I start at 2 instead of 1, that automatically excludes one of
> the factors. Then, by default, Python goes "to" the chosen count and
> not "through" the count, so just the syntax causes Python to rule out
> the other factor (the number itself).
>
> So this works:
> while True:
> a=random.randrange(1,8)
> print (a)
> for x in range(2,a):
> if a%x==0:
> print ("Number is not prime")
> break
> wait = input (" "*40 + "Wait")
>
> But, what this instructions want printed is "This is a prime number"
> So how to I use this code logic NOT print (not prime) and have the
> logic print "This number is prime"
>
>
One neat feature of Python is the for...else function. The code inside the
else block will run only if the loop ran to completion (untested code
follows):
while True:
a=random.randrange(1,8)
print (a)
for x in range(2,a):
if a%x==0:
print ("Number is not prime")
break
else:
print("Number is prime")
wait = input (" "*40 + "Wait")
Depending on how advanced you want to get (I know you are relatively new to
Python), another decent way would be to extract the prime check to a
function, and return the result, and print based on that result (again,
untested code):
def isPrime(number):
for x in range(2,a):
if a%x==0:
return False
return True
while True:
a=random.randrange(1,8)
print (a)
if isPrime(a):
print("Number is prime")
else:
print("Number is not prime")
wait = input (" "*40 + "Wait")
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On 09/05/2014 09:48 AM, Seymore4Head wrote:
I'm still doing practice problems. I haven't heard from the library
on any of the books I have requested.
http://www.practicepython.org/exercise/2014/04/16/11-check-primality-functions.html
This is not a hard problem, but it got me to thinking a little. A
prime number will divide by one and itself. When setting up this
loop, if I start at 2 instead of 1, that automatically excludes one of
the factors. Then, by default, Python goes "to" the chosen count and
not "through" the count, so just the syntax causes Python to rule out
the other factor (the number itself).
So this works:
while True:
a=random.randrange(1,8)
print (a)
for x in range(2,a):
if a%x==0:
print ("Number is not prime")
break
wait = input (" "*40 + "Wait")
But, what this instructions want printed is "This is a prime number"
So how to I use this code logic NOT print (not prime) and have the
logic print "This number is prime"
Python's 'for' loop has a handy 'else' extension which is perfect for the
search-type of 'for' loop:
while True:
a=random.randrange(1,8)
print (a)
for x in range(2,a):
if a%x==0:
print ("Number is not prime")
break
else:
print ("Number is prime")
wait = input (" "*40 + "Wait")
Note the two lines I added after the 'break' and before the 'wait'.
--
~Ethan~
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
Bob gailer
On Sep 5, 2014 12:51 PM, "Seymore4Head"
wrote:
>
> I'm still doing practice problems. I haven't heard from the library
> on any of the books I have requested.
>
>
http://www.practicepython.org/exercise/2014/04/16/11-check-primality-functions.html
>
> This is not a hard problem, but it got me to thinking a little. A
> prime number will divide by one and itself. When setting up this
> loop, if I start at 2 instead of 1, that automatically excludes one of
> the factors. Then, by default, Python goes "to" the chosen count and
> not "through" the count, so just the syntax causes Python to rule out
> the other factor (the number itself).
>
> So this works:
> while True:
> a=random.randrange(1,8)
> print (a)
> for x in range(2,a):
> if a%x==0:
> print ("Number is not prime")
> break
else:
print ...
> wait = input (" "*40 + "Wait")
>
> But, what this instructions want printed is "This is a prime number"
> So how to I use this code logic NOT print (not prime) and have the
> logic print "This number is prime"
>
> --
> https://mail.python.org/mailman/listinfo/python-list
--
https://mail.python.org/mailman/listinfo/python-list
Re: My backwards logic
On 2014-09-05 17:48, Seymore4Head wrote:
I'm still doing practice problems. I haven't heard from the library
on any of the books I have requested.
http://www.practicepython.org/exercise/2014/04/16/11-check-primality-functions.html
This is not a hard problem, but it got me to thinking a little. A
prime number will divide by one and itself. When setting up this
loop, if I start at 2 instead of 1, that automatically excludes one of
the factors. Then, by default, Python goes "to" the chosen count and
not "through" the count, so just the syntax causes Python to rule out
the other factor (the number itself).
So this works:
while True:
a=random.randrange(1,8)
print (a)
for x in range(2,a):
if a%x==0:
print ("Number is not prime")
break
wait = input (" "*40 + "Wait")
But, what this instructions want printed is "This is a prime number"
So how to I use this code logic NOT print (not prime) and have the
logic print "This number is prime"
Look for a factor. If you don't find one, it's a prime number.
--
https://mail.python.org/mailman/listinfo/python-list
My backwards logic
I'm still doing practice problems. I haven't heard from the library
on any of the books I have requested.
http://www.practicepython.org/exercise/2014/04/16/11-check-primality-functions.html
This is not a hard problem, but it got me to thinking a little. A
prime number will divide by one and itself. When setting up this
loop, if I start at 2 instead of 1, that automatically excludes one of
the factors. Then, by default, Python goes "to" the chosen count and
not "through" the count, so just the syntax causes Python to rule out
the other factor (the number itself).
So this works:
while True:
a=random.randrange(1,8)
print (a)
for x in range(2,a):
if a%x==0:
print ("Number is not prime")
break
wait = input (" "*40 + "Wait")
But, what this instructions want printed is "This is a prime number"
So how to I use this code logic NOT print (not prime) and have the
logic print "This number is prime"
--
https://mail.python.org/mailman/listinfo/python-list
