First Program Bug (Newbie)

[oog1e]

Hey, big thanks to you and Gabriel for replying. I couldn't quite follow 
what you did yet. What is this 'gimpy' thing and where can I read about 
it? In response:

First: Heh, I'm a little embarrassed I didn't notice this. I thought 'I 
only need to check up to half' but it didn't occur that base**2 was more 
than 1/2 candidate.

Second: I don't quite follow this.

Third: Yeah, I found that bug just before, and because of, posting.

Fourth: I used the incrementing command and incremented candidates by 
two to check only odds and now the program is a lot faster.

Thanks a lot for yall's replies. Three more things before I go. What is 
the square root function in python? I couldn't find the fact.py demo 
script. I didn't mean return I meant 'continue'.

Mensanator wrote:
> On Mar 17, 7:03 pm, Benjamin Serrato <benjamin.serr... at gmail.com>
> wrote:
>> I Found It!! The following was a post asking for help finding a bug. I
>> thought I needed help with my syntax, but just before sending I found
>> the bug on line 13. Line 13 should read: "base = 2". I would still
>> appreciate any comments on my program. Maybe there is a better way to do
>> it that I didn't think about. I know it's not that interesting but it's
>> my first one.
>>
>> [post]
>> I'm almost halfway through an online tutorial I found on the python.org
>> site and decided to stop and write a program for myself. I got it in my
>> head to write a program to print all the primes; the idea came from
>> another tutorial. The program prints some non-prime numbers. In a
>> comparison to lists of primes the program prints eight non-primes for
>> numbers less than 150. Those numbers are [27,35,87,95,119,123,143,147].
>> Here is the program.
>>
>> base = 2
>> candidate = 3
>>
>> while True:
>>         while candidate % base != 0:
>>                 base = base + 1
>>                 if base > (candidate / 2):
>>                         print candidate
>>                         candidate = candidate + 1
>>                         base = 2
>>         else:
>>                 candidate = candidate + 1
>>
>> The following is a rundown of the program.
>>
>> candidate: A possible prime number.
>> base: Start point for divisibility testing.
>> outer while loop: Causes the program to loop.
>> inner while loop: Obviously, checks if 'candidate' mod 'base' equals
>> zero. If not base is incremented by one then 'if loop'.
>> if loop: After base has been incremented this checks whether all the
>> possible divisors have been used up. If they have then 'candidate' must
>> be prime. So, candidate is printed, a new candidate is chosen and the
>> base is reset.
>> else loop: If 'candidate' mod 'base' equals zero, then 'candidate' is
>> not prime and a new candidate is chosen.
>>
>> I realize yall probably didn't need all that.
>>
>> At first I tried to use 'return' on the 'else' block to cause the
>> program to loop, but I don't understand 'return' yet and that didn't
>> work. So, I put the rest into another while loop and was really happy to
>> find it worked but the program prints some non-prime numbers.
>>
>> Thanks, Benjamin Serrato
>>
>> P.S. What is the chance I'll get spam for using my real email address? I
>> currently don't get any so...
>> [/post]
> 
> Several items.
> 
> First, you don't need to check base larger than sqrt(candidate).
> 
> Second, see comments following dc.
> 
> Third, you need to add base = 2 to end of program, otherwise next
> candidate starts base where previous candidate left off.
> 
> Fourth, use +=1 to increment.
> 
> Finally, throw this away and use gmpy. :-)
> 
> 
> import gmpy  # for Quality Assurance
> base = 2
> candidate = 3
> p = 0                            # prime count
> while p<100:                     # limit the loop to 100 primes
>   while candidate % base != 0:
>     base += 1
>     #if base > (candidate / 2):
>     if base > (gmpy.sqrt(candidate)):  # only need to test to
> sqrt(candidate)
>       dc = divmod(candidate,2)         # remainder==0 gives false
> primes
>       if dc[1]==1:
>         #
>         # the gmpy functions are for QA, verifies that what you call a
> prime
>         # really is one and the next_prime makes sure you don't skip
> any
>         # these can be removed once working
>         #
>         print
> candidate,gmpy.is_prime(candidate)>0,gmpy.next_prime(candidate)
>         p += 1
>         candidate += 1
>         base = 2
>       else:
>         candidate += 1                 # false prime, reset
>         base = 2
>   else:
>     candidate += 1
>     base = 2                           # failure to reset causes false
> primes
> 
> ##  3 True 5
> ##  5 True 7
> ##  7 True 11
> ##  11 True 13
> ##  13 True 17
> ##  17 True 19
> ##  19 True 23
> ##  23 True 29
> ##  29 True 31
> ##  31 True 37
> ##  37 True 41
> ##  41 True 43
> ##  43 True 47
> ##  47 True 53
> ##  53 True 59
> ##  59 True 61
> ##  61 True 67
> ##  67 True 71
> ##  71 True 73
> ##  73 True 79
> ##  79 True 83
> ##  83 True 89
> ##  89 True 97
> ##  97 True 101
> ##  101 True 103
> ##  103 True 107
> ##  107 True 109
> ##  109 True 113
> ##  113 True 127
> ##  127 True 131
> ##  131 True 137
> ##  137 True 139
> ##  139 True 149
> ##  149 True 151
> ##  151 True 157
> ##  157 True 163
> ##  163 True 167
> ##  167 True 173
> ##  173 True 179
> ##  179 True 181
> ##  181 True 191
> ##  191 True 193
> ##  193 True 197
> ##  197 True 199
> ##  199 True 211
> ##  211 True 223
> ##  223 True 227
> ##  227 True 229
> ##  229 True 233
> ##  233 True 239
> ##  239 True 241
> ##  241 True 251
> ##  251 True 257
> ##  257 True 263
> ##  263 True 269
> ##  269 True 271
> ##  271 True 277
> ##  277 True 281
> ##  281 True 283
> ##  283 True 293
> ##  293 True 307
> ##  307 True 311
> ##  311 True 313
> ##  313 True 317
> ##  317 True 331
> ##  331 True 337
> ##  337 True 347
> ##  347 True 349
> ##  349 True 353
> ##  353 True 359
> ##  359 True 367
> ##  367 True 373
> ##  373 True 379
> ##  379 True 383
> ##  383 True 389
> ##  389 True 397
> ##  397 True 401
> ##  401 True 409
> ##  409 True 419
> ##  419 True 421
> ##  421 True 431
> ##  431 True 433
> ##  433 True 439
> ##  439 True 443
> ##  443 True 449
> ##  449 True 457
> ##  457 True 461
> ##  461 True 463
> ##  463 True 467
> ##  467 True 479
> ##  479 True 487
> ##  487 True 491
> ##  491 True 499
> ##  499 True 503
> ##  503 True 509
> ##  509 True 521
> ##  521 True 523
> ##  523 True 541
> ##  541 True 547
> ##  547 True 557