# 1000th prime test is incorrect

• (3 Pages)
• 1
• 2
• 3

## 39 Replies - 1657 Views - Last Post: 01 March 2018 - 08:30 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=409264&amp;s=7ec5a5cc880865cb5db313843e3e5d2d&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #16 Zhme

Reputation: 5
• Posts: 75
• Joined: 02-August 15

## Re: 1000th prime test is incorrect

Posted 15 February 2018 - 01:42 PM

I had noticed the difference when using factors of 64 and I wrote some new code with high hopes for success.

```import math
import itertools

primes = []
primeTest = 27
counter = 0

while counter < 15:
for primeTest in range(1, 50, 2):
for divisor in range(3, (int(math.sqrt(primeTest) + 1))):
counter += 1
print("test:", primeTest, "\tdivisor:", divisor)
if primeTest % divisor == 0:
primes.append(primeTest)

print(primes)

```

Here is my new and improved test for primality, if you notice the
```== 0
```
, that was only to see if I was mistaken with my logic for modulus testing..

It generates a list of some primes when using the
``` != 0
```
but still has the addition of non prime numbers x[.

I think I may be appending the primeTest variable at the wrong place.

### #17 Zhme

Reputation: 5
• Posts: 75
• Joined: 02-August 15

## Re: 1000th prime test is incorrect

Posted 15 February 2018 - 02:46 PM

So i'm almost there, I hope:

```import math
import itertools

primes = []
counter = 0

while counter < 15:
for primeTest in range(1, 30, 2):
for divisor in range(3, (int(math.sqrt(primeTest))) + 1, 2):
counter += 1
print("test:", primeTest, "\tdivisor:", divisor,
"prime % divis =", (primeTest % divisor))
if primeTest % divisor != 0:
primes.append(primeTest)

else:
break

print(primes)

```

The final print statement does print MOSTLY primes but there are still some additional non-prime numbers that are baffling me that they would be appended T_T

I added this to the end:

```for value in primes:
for i in range(3, (int(math.sqrt(value))) + 1, 2):
if value % i == 0:
primes.remove(value)
else:
continue

print(primes)

```

and I believe that rid myself of the lingering primality testing errors... but this is so very painfully uneleagant, no where near as simple as I hoped to write this out x|

### #18 DK3250

• Pythonian

Reputation: 607
• Posts: 1,927
• Joined: 27-December 13

## Re: 1000th prime test is incorrect

Posted 15 February 2018 - 04:46 PM

As I mentioned in post #6, you logic is wrong - this is why your code produce a wrong list of primes.

In line 14 and 15 (in your last post) you checkif primeTest % divisor != 0: and at first true instance you add primeTest to the list.
This is wrong..!
Only if the test is true for all divisors should primeTest be accepted.

Example:
primeTest = 25
divisor = 3

primeTest % divisor = 1
...and you add 25 to the list

This overlooks the fact that 25 % 5 == 0 and 25 should NOT be added to the list.

Another thing:
If you really want prime number 1000, it is important to notice that first prime is 2.
1 is not a prime by definition.

### #19 DK3250

• Pythonian

Reputation: 607
• Posts: 1,927
• Joined: 27-December 13

## Re: 1000th prime test is incorrect

Posted 16 February 2018 - 09:17 AM

Let me give you just a small hint. You test
```if primeTest % divisor != 0:

```
..and as I demonstrated in my last post you will need to test all possible divisors. This is tedious.

Now, if you test the opposite condition:
```if primeTest % divisor == 0:

```
..then you immediately know that 'primeTest' is not a prime and you can proceed to next 'primeTest'

Contrary, if you exhaust the range without finding a divisor then 'primeTest' must be prime.

### #20 jon.kiparsky

• Beginner

Reputation: 12311
• Posts: 20,907
• Joined: 19-March 11

## Re: 1000th prime test is incorrect

Posted 16 February 2018 - 09:28 AM

You might want to read this blog entry and see if it helps.

### #21 Zhme

Reputation: 5
• Posts: 75
• Joined: 02-August 15

## Re: 1000th prime test is incorrect

Posted 16 February 2018 - 12:31 PM

jon.kiparsky, on 16 February 2018 - 10:28 AM, said:

You might want to read this blog entry and see if it helps.

I will read this thoroughly, I don't want to use other Python Help posts to get my logic errors fixed. I want to understand it for myself, I need to have my epiphany in writing the program myself or I will never learn. I will only be using others to solve my own problems.

Currently, with the loop and trial by error methods that I have been trying not giving me proper results, I have decided to take a look at the Sieve's, like the famed Eratosthenes />/>

Without citing another's attempt at writing a sieve I would like to show you my first attempts at my "from scratch", ideas:

```primes = []
populate = []

for i in range(2, 800):
populate.append(i)
for prime in
for num in populate:
if num % 2 == 0:
populate.remove(num)
primes.append(num)

for num in populate:
if num % 3 == 0:
populate.remove(num)
primes.append(num)

for num in populate:
if num % 5 == 0:
populate.remove(num)

for num in populate:
if num % 7 == 0:
populate.remove(num)

for num in populate:
if num % 11 == 0:
populate.remove(num)

for num in populate:
if num % 13 == 0:
populate.remove(num)

for num in populate:
if num % 17 == 0:
populate.remove(num)

for num in populate:
if num % 19 == 0:
populate.remove(num)

print(populate)
print(primes)

```

I know in that code snippet there are loops and for tests that make no sense logically, but they are for testing purposes to see what is happening where and why.

Thank you for the response. I will get back to that blog post now!

I perused over the first section of the blog, the second half uses variables like m, p, q and s which make it hard for me to mull over. I'll have to reread it a few times, but I understand the general concept of divisors becoming redundant over the tested number/2.

here is my isPrime function:
```def isPrime(test):
for divisor in range(2, test - 1):
if test % divisor == 0:
return False
else:
return True

print(isPrime(16))

```

Still confused about how to employ it into a for/while/any loop which can test all primes up to the thousandth though :scratcheshead:

This post has been edited by Zhme: 16 February 2018 - 12:55 PM

### #22 DK3250

• Pythonian

Reputation: 607
• Posts: 1,927
• Joined: 27-December 13

## Re: 1000th prime test is incorrect

Posted 16 February 2018 - 12:38 PM

Sieves are definitely more complicated than your original approach.
Why not finish this off - you were not so far from a solution...

If you really want to learn; then, abandoning a task just before completion is an inefficient strategy.

### #23 Zhme

Reputation: 5
• Posts: 75
• Joined: 02-August 15

## Re: 1000th prime test is incorrect

Posted 16 February 2018 - 01:08 PM

DK3250, on 16 February 2018 - 01:38 PM, said:

Sieves are definitely more complicated than your original approach.
Why not finish this off - you were not so far from a solution...

If you really want to learn; then, abandoning a task just before completion is an inefficient strategy.

I agree, I most definitely will not be abandoning the first approach. I was only trying to look at a different method so that I could try and wrap my head around the process of finding primes in a different way. Unsuccessfully, to find out how my method wasn't working xD

### #24 DK3250

• Pythonian

Reputation: 607
• Posts: 1,927
• Joined: 27-December 13

## Re: 1000th prime test is incorrect

Posted 16 February 2018 - 01:09 PM

I see jon.kiparsky is also active, so you may get something similar from him also.

Let's go through you code:
```def isPrime(test):
for divisor in range(2, test - 1):  # here you go through all numbers - in earlier versions you did range(3, sqrt(test)+1, 2) which is better !!
if test % divisor == 0:
return False  # yes..!
else:  # only return True if ALL divisors do not divide - small modification required here...
return True
```

This post has been edited by DK3250: 16 February 2018 - 01:10 PM

### #25 Zhme

Reputation: 5
• Posts: 75
• Joined: 02-August 15

## Re: 1000th prime test is incorrect

Posted 16 February 2018 - 01:09 PM

```def isPrime(test):
for divisor in range(2, test - 1):
if test % divisor == 0:
return False
else:
return True

primes = []

for prime in range(1, 50):
if isPrime(prime):
primes.append(prime)

print(primes)

```

so this addition for using the isPrime function to test over a given loop seems to only be appending every odd integer from 5 upwards?

### #26 Zhme

Reputation: 5
• Posts: 75
• Joined: 02-August 15

## Re: 1000th prime test is incorrect

Posted 16 February 2018 - 01:20 PM

DK3250, on 16 February 2018 - 01:38 PM, said:

To my surprise it is much faster to loop through all uneven numbers in range(3, int(sqrt(candidate))+1, 2)

How can I apply that to my isPrime function, if that is at all possible?

Didn't see this.... hold on while I do some adjustments

DK3250, on 16 February 2018 - 02:09 PM, said:

I see jon.kiparsky is also active, so you may get something similar from him also.

Let's go through you code:
```def isPrime(test):
for divisor in range(2, test - 1):  # here you go through all numbers - in earlier versions you did range(3, sqrt(test)+1, 2) which is better !!
if test % divisor == 0:
return False  # yes..!
else:  # only return True if ALL divisors do not divide - small modification required here...
return True
```

This post has been edited by Zhme: 16 February 2018 - 01:23 PM

### #27 DK3250

• Pythonian

Reputation: 607
• Posts: 1,927
• Joined: 27-December 13

## Re: 1000th prime test is incorrect

Posted 16 February 2018 - 01:25 PM

You already did in post #17

sorry - our mail are crossing....

### #28 Zhme

Reputation: 5
• Posts: 75
• Joined: 02-August 15

## Re: 1000th prime test is incorrect

Posted 16 February 2018 - 01:38 PM

```import math

def isPrime(test):
for divisor in range(3, int(math.sqrt(test)) + 1, 2):
if test % divisor == 0:
return False
else:
return True

print(isPrime(3))

```

For some reason, this outputs None...

and I also tried 494, which output True??

### #29 DK3250

• Pythonian

Reputation: 607
• Posts: 1,927
• Joined: 27-December 13

## Re: 1000th prime test is incorrect

Posted 16 February 2018 - 01:46 PM

The condition for returning False is ok.
When is it you want the function to return True? You need a (quite small) modification here...
Give it one more try..!

### #30 Zhme

Reputation: 5
• Posts: 75
• Joined: 02-August 15

## Re: 1000th prime test is incorrect

Posted 16 February 2018 - 02:10 PM

Starting to feel like I am not as smart as I thought I was x(
```def isPrime(test):
for divisor in range(3, int(math.sqrt(test)) + 1, 2):
if test % divisor == 0:
return False
for i in range(divisor, int(math.sqrt(test)) + 1, 2):
if divisor % i != 0:
return False

```

Worked well in some cases but not all.

I'm going to do this on paper to test my math and see where this logic is breaking...
[/edit]

This post has been edited by Zhme: 16 February 2018 - 02:19 PM