Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #77590 > unrolled thread

My backwards logic

Back to article view | Back to comp.lang.python

Contents

  My backwards logic Seymore4Head <Seymore4Head@Hotmail.invalid> - 2014-09-05 12:48 -0400
    Re: My backwards logic MRAB <python@mrabarnett.plus.com> - 2014-09-05 17:57 +0100
    Re: My backwards logic Bob Gailer <bgailer@gmail.com> - 2014-09-05 13:04 -0400
    Re: My backwards logic John Gordon <gordon@panix.com> - 2014-09-05 17:08 +0000
    Re: My backwards logic Ethan Furman <ethan@stoneleaf.us> - 2014-09-05 10:08 -0700
      Re: My backwards logic Seymore4Head <Seymore4Head@Hotmail.invalid> - 2014-09-05 13:44 -0400
        Re: My backwards logic Chris Kaynor <ckaynor@zindagigames.com> - 2014-09-05 11:17 -0700
        Re: My backwards logic Ian Kelly <ian.g.kelly@gmail.com> - 2014-09-05 15:04 -0600
        Re: My backwards logic Chris Angelico <rosuav@gmail.com> - 2014-09-06 09:44 +1000
    Re: My backwards logic Chris Kaynor <ckaynor@zindagigames.com> - 2014-09-05 10:09 -0700
    Re:My backwards logic Dave Angel <davea@davea.name> - 2014-09-05 13:15 -0400
    Re: My backwards logic Ian Kelly <ian.g.kelly@gmail.com> - 2014-09-05 11:17 -0600
    Re: My backwards logic Juan Christian <juan0christian@gmail.com> - 2014-09-05 14:35 -0300
    Re: My backwards logic Ethan Furman <ethan@stoneleaf.us> - 2014-09-05 11:41 -0700
    Re: My backwards logic MRAB <python@mrabarnett.plus.com> - 2014-09-05 19:48 +0100
    Re: My backwards logic Juan Christian <juan0christian@gmail.com> - 2014-09-05 16:34 -0300
      Re: My backwards logic Paul Rubin <no.email@nospam.invalid> - 2014-09-05 13:07 -0700
        Re: My backwards logic Rustom Mody <rustompmody@gmail.com> - 2014-09-05 18:24 -0700
    Re: My backwards logic Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-09-05 20:54 +0100
    Re: My backwards logic Seymore4Head <Seymore4Head@Hotmail.invalid> - 2014-09-05 17:49 -0400
      Re: My backwards logic Chris Kaynor <ckaynor@zindagigames.com> - 2014-09-05 15:14 -0700
        Re: My backwards logic Seymore4Head <Seymore4Head@Hotmail.invalid> - 2014-09-05 18:36 -0400
      Re: My backwards logic Ian Kelly <ian.g.kelly@gmail.com> - 2014-09-05 16:35 -0600
        Re: My backwards logic Seymore4Head <Seymore4Head@Hotmail.invalid> - 2014-09-05 19:05 -0400
      Re: My backwards logic Dave Angel <davea@davea.name> - 2014-09-05 23:10 -0400
    Re: My backwards logic Juan Christian <juan0christian@gmail.com> - 2014-09-05 22:54 -0300
      Re: My backwards logic Rustom Mody <rustompmody@gmail.com> - 2014-09-05 18:58 -0700
    Posting style: interleaved responses (was: My backwards logic) Ben Finney <ben+python@benfinney.id.au> - 2014-09-06 12:37 +1000
    Re: Posting style: interleaved responses (was: My backwards logic) Juan Christian <juan0christian@gmail.com> - 2014-09-06 00:06 -0300
    Re: Posting style: interleaved responses (was: My backwards logic) Zachary Ware <zachary.ware+pylist@gmail.com> - 2014-09-05 23:04 -0500
    Re: My backwards logic Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-09-06 08:45 +0100
    Re: My backwards logic Denis McMahon <denismfmcmahon@gmail.com> - 2014-09-06 07:49 +0000
      Prime testing [was Re: My backwards logic] Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-06 20:38 +1000
        Re: Prime testing [was Re: My backwards logic] Chris Angelico <rosuav@gmail.com> - 2014-09-06 20:42 +1000
        Re: Prime testing [was Re: My backwards logic] Manolo Martínez <manolo@austrohungaro.com> - 2014-09-06 12:53 +0200
          Re: Prime testing [was Re: My backwards logic] Peter Pearson <pkpearson@nowhere.invalid> - 2014-09-07 18:53 +0000
            Re: Prime testing [was Re: My backwards logic] Manolo Martínez <manolo@austrohungaro.com> - 2014-09-07 21:09 +0200
            Re: Prime testing [was Re: My backwards logic] Dan Stromberg <drsalists@gmail.com> - 2014-09-07 20:23 -0700
    Re: Posting style: interleaved responses Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-09-06 08:46 +0100

Page 2 of 2 — ← Prev page 1 [2]

#77621

[Multipart message — attachments visible in raw view] — view raw

On Fri, Sep 5, 2014 at 2:49 PM, Seymore4Head <Seymore4Head@hotmail.invalid>
wrote:

> On Fri, 05 Sep 2014 12:48:56 -0400, Seymore4Head
> <Seymore4Head@Hotmail.invalid> 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

[toc] | [prev] | [next] | [standalone]

#77624

On Fri, 5 Sep 2014 15:14:41 -0700, Chris Kaynor
<ckaynor@zindagigames.com> wrote:

>On Fri, Sep 5, 2014 at 2:49 PM, Seymore4Head <Seymore4Head@hotmail.invalid>
>wrote:
>
>> On Fri, 05 Sep 2014 12:48:56 -0400, Seymore4Head
>> <Seymore4Head@Hotmail.invalid> 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

[toc] | [prev] | [next] | [standalone]

#77623

On Fri, Sep 5, 2014 at 3:49 PM, Seymore4Head
<Seymore4Head@hotmail.invalid> 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.

[toc] | [prev] | [next] | [standalone]

#77625

On Fri, 5 Sep 2014 16:35:18 -0600, Ian Kelly <ian.g.kelly@gmail.com>
wrote:

>On Fri, Sep 5, 2014 at 3:49 PM, Seymore4Head
><Seymore4Head@hotmail.invalid> 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

[toc] | [prev] | [next] | [standalone]

#77633

Seymore4Head <Seymore4Head@Hotmail.invalid> Wrote in message:
> On Fri, 05 Sep 2014 12:48:56 -0400, Seymore4Head
> <Seymore4Head@Hotmail.invalid> 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

[toc] | [prev] | [next] | [standalone]

#77629

[Multipart message — attachments visible in raw view] — view raw

@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 <breamoreboy@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.
>
> --
> 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
>

[toc] | [prev] | [next] | [standalone]

#77630

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

[toc] | [prev] | [next] | [standalone]

#77631 — Posting style: interleaved responses (was: My backwards logic)

Juan Christian <juan0christian@gmail.com> 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”
<URL: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

[toc] | [prev] | [next] | [standalone]

#77632 — Re: Posting style: interleaved responses (was: My backwards logic)

[Multipart message — attachments visible in raw view] — view raw

On Fri, Sep 5, 2014 at 11:37 PM, Ben Finney <ben+python@benfinney.id.au>
wrote:

> Juan Christian <juan0christian@gmail.com> 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”
> <URL: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.

[toc] | [prev] | [next] | [standalone]

#77634 — Re: Posting style: interleaved responses (was: My backwards logic)

On Fri, Sep 5, 2014 at 10:06 PM, Juan Christian
<juan0christian@gmail.com> wrote:
> On Fri, Sep 5, 2014 at 11:37 PM, Ben Finney <ben+python@benfinney.id.au>
> wrote:
>>
>> Juan Christian <juan0christian@gmail.com> 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”
>> <URL: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

[toc] | [prev] | [next] | [standalone]

#77640

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 <breamoreboy@yahoo.co.uk
> <mailto:breamoreboy@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

[toc] | [prev] | [next] | [standalone]

#77641

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, denismfmcmahon@gmail.com

[toc] | [prev] | [next] | [standalone]

#77647 — 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
(500000.0, 333333.3333333333, 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

[toc] | [prev] | [next] | [standalone]

#77648 — Re: Prime testing [was Re: My backwards logic]

On Sat, Sep 6, 2014 at 8:38 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> 3, 5, 7, 9 is a waste of time, 11, 13, 15 is a waste of time, ...

I love this sequence.

ChrisA

[toc] | [prev] | [next] | [standalone]

#77658 — 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

[toc] | [prev] | [next] | [standalone]

#77680 — 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.

[toc] | [prev] | [next] | [standalone]

#77682 — 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 :/

[toc] | [prev] | [next] | [standalone]

#77692 — Re: Prime testing [was Re: My backwards logic]

On Sun, Sep 7, 2014 at 11:53 AM, Peter Pearson
<pkpearson@nowhere.invalid> 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.

[toc] | [prev] | [next] | [standalone]

#77642 — Re: Posting style: interleaved responses

On 06/09/2014 05:04, Zachary Ware wrote:
>
> 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" :)
>

+1 :)

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.python

csiph-web