Project Euler 357 prime number generator in Python 3
Clash Royale CLAN TAG#URR8PPP
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;
up vote
7
down vote
favorite
I'm brute forcing the Project Euler 357 since no better algorithm comes to my mind. The challenge asks:
Find the sum of all positive integers n not exceeding 108 such that for every divisor d of n, d+n/d is prime.
The code is this:
#!/bin/env python3
import time
import math
"""
https://projecteuler.net/problem=357
"""
start = time.time()
def primes(ubound=10**5):
""" Generating prime numbers LIST
https://stackoverflow.com/a/8627193/1770460
"""
size = (ubound - 3) // 2
a = [False] * size
s = 0
primes =
while s < size:
t = 2 * s
p = t + 3
primes.append(p)
for n in range(t * (s + 3) + 3, size, p):
a[n] = True
s = s + 1
while s < size and a[s]:
s = s + 1
return primes
the_primes = primes()
def number_divisors(max_limit=10**5):
""" Find the divisors of every number.
Return it in a dict in the format:
number1: [divisor1, divisor2 ... ], ..
"""
num_divs =
for i in range(4, max_limit):
if i in the_primes:
continue
else:
sq = math.sqrt(i)
for n in range(2, int(sq) + 1):
if i not in num_divs:
num_divs[i] = [1]
if i % n == 0:
if n == i / n:
num_divs[i].append(n)
else:
num_divs[i].extend((n, i / n))
return num_divs
def find_count(d):
""" Check every number whether the divisors i.e. d + number / d is
prime.
"""
assert d is not None
count = 0
for number, list_divisors in d.items():
all_primes = True
for each_div in list_divisors:
val = (each_div + (number / each_div))
if val not in the_primes:
all_primes = False
break
if all_primes:
count += 1
return count
if __name__ == '__main__':
num_divisors = number_divisors()
print(find_count(num_divisors))
elapsed_time = (time.time() - start)
print('time elapsed %s sec.' % elapsed_time)
Profiling the script shows that the find_count
is the first bottleneck and by advice of other answers the values should be cached(?) somehow.
$ python3 -m cProfile 357.py
275
time elapsed 167.41558241844177 sec.
583580 function calls in 167.416 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 167.416 167.416 357.py:3(<module>)
1 0.020 0.020 0.020 0.020 357.py:30(primes)
1 24.526 24.526 24.740 24.740 357.py:51(number_divisors)
1 142.655 142.655 142.655 142.655 357.py:75(find_count)
Any advice on how to improve find_count()
?
python python-3.x programming-challenge primes memoization
add a comment |Â
up vote
7
down vote
favorite
I'm brute forcing the Project Euler 357 since no better algorithm comes to my mind. The challenge asks:
Find the sum of all positive integers n not exceeding 108 such that for every divisor d of n, d+n/d is prime.
The code is this:
#!/bin/env python3
import time
import math
"""
https://projecteuler.net/problem=357
"""
start = time.time()
def primes(ubound=10**5):
""" Generating prime numbers LIST
https://stackoverflow.com/a/8627193/1770460
"""
size = (ubound - 3) // 2
a = [False] * size
s = 0
primes =
while s < size:
t = 2 * s
p = t + 3
primes.append(p)
for n in range(t * (s + 3) + 3, size, p):
a[n] = True
s = s + 1
while s < size and a[s]:
s = s + 1
return primes
the_primes = primes()
def number_divisors(max_limit=10**5):
""" Find the divisors of every number.
Return it in a dict in the format:
number1: [divisor1, divisor2 ... ], ..
"""
num_divs =
for i in range(4, max_limit):
if i in the_primes:
continue
else:
sq = math.sqrt(i)
for n in range(2, int(sq) + 1):
if i not in num_divs:
num_divs[i] = [1]
if i % n == 0:
if n == i / n:
num_divs[i].append(n)
else:
num_divs[i].extend((n, i / n))
return num_divs
def find_count(d):
""" Check every number whether the divisors i.e. d + number / d is
prime.
"""
assert d is not None
count = 0
for number, list_divisors in d.items():
all_primes = True
for each_div in list_divisors:
val = (each_div + (number / each_div))
if val not in the_primes:
all_primes = False
break
if all_primes:
count += 1
return count
if __name__ == '__main__':
num_divisors = number_divisors()
print(find_count(num_divisors))
elapsed_time = (time.time() - start)
print('time elapsed %s sec.' % elapsed_time)
Profiling the script shows that the find_count
is the first bottleneck and by advice of other answers the values should be cached(?) somehow.
$ python3 -m cProfile 357.py
275
time elapsed 167.41558241844177 sec.
583580 function calls in 167.416 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 167.416 167.416 357.py:3(<module>)
1 0.020 0.020 0.020 0.020 357.py:30(primes)
1 24.526 24.526 24.740 24.740 357.py:51(number_divisors)
1 142.655 142.655 142.655 142.655 357.py:75(find_count)
Any advice on how to improve find_count()
?
python python-3.x programming-challenge primes memoization
1
I do not remember solving this issue so I do not have an algorithmic truck for that one. It won't make a huge difference but you'd benefit from using divmod to have both quotient and remainder....
â Josay
Feb 24 at 17:38
1
1 is a factor of all numbers. Hence, you will be testing (1 + n/1) for primality. Consider what happens if n is odd and > 1? There are further simplifications possible, but this is the most obvious.
â rossum
Mar 2 at 12:39
add a comment |Â
up vote
7
down vote
favorite
up vote
7
down vote
favorite
I'm brute forcing the Project Euler 357 since no better algorithm comes to my mind. The challenge asks:
Find the sum of all positive integers n not exceeding 108 such that for every divisor d of n, d+n/d is prime.
The code is this:
#!/bin/env python3
import time
import math
"""
https://projecteuler.net/problem=357
"""
start = time.time()
def primes(ubound=10**5):
""" Generating prime numbers LIST
https://stackoverflow.com/a/8627193/1770460
"""
size = (ubound - 3) // 2
a = [False] * size
s = 0
primes =
while s < size:
t = 2 * s
p = t + 3
primes.append(p)
for n in range(t * (s + 3) + 3, size, p):
a[n] = True
s = s + 1
while s < size and a[s]:
s = s + 1
return primes
the_primes = primes()
def number_divisors(max_limit=10**5):
""" Find the divisors of every number.
Return it in a dict in the format:
number1: [divisor1, divisor2 ... ], ..
"""
num_divs =
for i in range(4, max_limit):
if i in the_primes:
continue
else:
sq = math.sqrt(i)
for n in range(2, int(sq) + 1):
if i not in num_divs:
num_divs[i] = [1]
if i % n == 0:
if n == i / n:
num_divs[i].append(n)
else:
num_divs[i].extend((n, i / n))
return num_divs
def find_count(d):
""" Check every number whether the divisors i.e. d + number / d is
prime.
"""
assert d is not None
count = 0
for number, list_divisors in d.items():
all_primes = True
for each_div in list_divisors:
val = (each_div + (number / each_div))
if val not in the_primes:
all_primes = False
break
if all_primes:
count += 1
return count
if __name__ == '__main__':
num_divisors = number_divisors()
print(find_count(num_divisors))
elapsed_time = (time.time() - start)
print('time elapsed %s sec.' % elapsed_time)
Profiling the script shows that the find_count
is the first bottleneck and by advice of other answers the values should be cached(?) somehow.
$ python3 -m cProfile 357.py
275
time elapsed 167.41558241844177 sec.
583580 function calls in 167.416 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 167.416 167.416 357.py:3(<module>)
1 0.020 0.020 0.020 0.020 357.py:30(primes)
1 24.526 24.526 24.740 24.740 357.py:51(number_divisors)
1 142.655 142.655 142.655 142.655 357.py:75(find_count)
Any advice on how to improve find_count()
?
python python-3.x programming-challenge primes memoization
I'm brute forcing the Project Euler 357 since no better algorithm comes to my mind. The challenge asks:
Find the sum of all positive integers n not exceeding 108 such that for every divisor d of n, d+n/d is prime.
The code is this:
#!/bin/env python3
import time
import math
"""
https://projecteuler.net/problem=357
"""
start = time.time()
def primes(ubound=10**5):
""" Generating prime numbers LIST
https://stackoverflow.com/a/8627193/1770460
"""
size = (ubound - 3) // 2
a = [False] * size
s = 0
primes =
while s < size:
t = 2 * s
p = t + 3
primes.append(p)
for n in range(t * (s + 3) + 3, size, p):
a[n] = True
s = s + 1
while s < size and a[s]:
s = s + 1
return primes
the_primes = primes()
def number_divisors(max_limit=10**5):
""" Find the divisors of every number.
Return it in a dict in the format:
number1: [divisor1, divisor2 ... ], ..
"""
num_divs =
for i in range(4, max_limit):
if i in the_primes:
continue
else:
sq = math.sqrt(i)
for n in range(2, int(sq) + 1):
if i not in num_divs:
num_divs[i] = [1]
if i % n == 0:
if n == i / n:
num_divs[i].append(n)
else:
num_divs[i].extend((n, i / n))
return num_divs
def find_count(d):
""" Check every number whether the divisors i.e. d + number / d is
prime.
"""
assert d is not None
count = 0
for number, list_divisors in d.items():
all_primes = True
for each_div in list_divisors:
val = (each_div + (number / each_div))
if val not in the_primes:
all_primes = False
break
if all_primes:
count += 1
return count
if __name__ == '__main__':
num_divisors = number_divisors()
print(find_count(num_divisors))
elapsed_time = (time.time() - start)
print('time elapsed %s sec.' % elapsed_time)
Profiling the script shows that the find_count
is the first bottleneck and by advice of other answers the values should be cached(?) somehow.
$ python3 -m cProfile 357.py
275
time elapsed 167.41558241844177 sec.
583580 function calls in 167.416 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 167.416 167.416 357.py:3(<module>)
1 0.020 0.020 0.020 0.020 357.py:30(primes)
1 24.526 24.526 24.740 24.740 357.py:51(number_divisors)
1 142.655 142.655 142.655 142.655 357.py:75(find_count)
Any advice on how to improve find_count()
?
python python-3.x programming-challenge primes memoization
edited Feb 25 at 1:50
Jamalâ¦
30.1k11114225
30.1k11114225
asked Feb 24 at 16:50
Bor
17517
17517
1
I do not remember solving this issue so I do not have an algorithmic truck for that one. It won't make a huge difference but you'd benefit from using divmod to have both quotient and remainder....
â Josay
Feb 24 at 17:38
1
1 is a factor of all numbers. Hence, you will be testing (1 + n/1) for primality. Consider what happens if n is odd and > 1? There are further simplifications possible, but this is the most obvious.
â rossum
Mar 2 at 12:39
add a comment |Â
1
I do not remember solving this issue so I do not have an algorithmic truck for that one. It won't make a huge difference but you'd benefit from using divmod to have both quotient and remainder....
â Josay
Feb 24 at 17:38
1
1 is a factor of all numbers. Hence, you will be testing (1 + n/1) for primality. Consider what happens if n is odd and > 1? There are further simplifications possible, but this is the most obvious.
â rossum
Mar 2 at 12:39
1
1
I do not remember solving this issue so I do not have an algorithmic truck for that one. It won't make a huge difference but you'd benefit from using divmod to have both quotient and remainder....
â Josay
Feb 24 at 17:38
I do not remember solving this issue so I do not have an algorithmic truck for that one. It won't make a huge difference but you'd benefit from using divmod to have both quotient and remainder....
â Josay
Feb 24 at 17:38
1
1
1 is a factor of all numbers. Hence, you will be testing (1 + n/1) for primality. Consider what happens if n is odd and > 1? There are further simplifications possible, but this is the most obvious.
â rossum
Mar 2 at 12:39
1 is a factor of all numbers. Hence, you will be testing (1 + n/1) for primality. Consider what happens if n is odd and > 1? There are further simplifications possible, but this is the most obvious.
â rossum
Mar 2 at 12:39
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
The most obvious improvement is to notice that if i in the_primes
and if val not in the_primes
both take $mathcalO(n)$ time. If you made the_primes
a set
instead of a list
it would only be $mathcalO(1)$. So just write:
the_primes = set(primes())
Also note that your "prime number generator" is not actually a Python generator. For that you would need to add a yield
:
def primes(ubound=10**5):
""" Generating prime numbers https://stackoverflow.com/a/8627193/1770460 """
size = (ubound - 3) // 2
a = [False] * size
s = 0
while s < size:
t = 2 * s
p = t + 3
yield p
for n in range(t * (s + 3) + 3, size, p):
a[n] = True
s = s + 1
while s < size and a[s]:
s = s + 1
The set()
call will then consume the generator. This will not make your code run faster, though (it needs about the same CPU) It might save you some memory, because you don't need the conversion from the internal list to the external set
.
Your original code takes about 43.5s on my machine. With the two changes in this post this drops down to less than 1.7s:
$ python3 -m cProfile 357.py
275
time elapsed 1.6228196620941162 sec.
583585 function calls in 1.623 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
...
9592 0.011 0.000 0.011 0.000 euler_357.py:14(primes)
1 0.001 0.001 1.623 1.623 euler_357.py:3(<module>)
1 1.524 1.524 1.584 1.584 euler_357.py:34(number_divisors)
1 0.026 0.026 0.026 0.026 euler_357.py:56(find_count)
...
alternatively, you could make your prime sieve add to a set rather than to a list and then convert to set.
â Oscar Smith
Feb 24 at 21:25
@OscarSmith Yeah, or make it a generator and consume it withset()
. Not much difference since the primes are all unique, of course. But it might save some memory since the internal datastructure is not needed.
â Graipher
Feb 24 at 21:27
Good idea about the sieve, it's an improvement.
â Bor
Feb 25 at 9:31
add a comment |Â
up vote
1
down vote
It's worth doing a bit of mathematics before embarking on a brute-force search. In order not to spoil the problem, I'll give a couple of hints.
Hint 1
If $n$ satisfies the condition of the problem, then for every divisor $d$ of $n$, it must be the case that $d + nover d$ is prime. Are there any divisors of $n$ that you already know about (without having to factorize $n$)? What therefore can you conclude about $n$?
Hint 2
If $n$ satisfies the condition of the problem, can it be the case that $n$ has a repeated factor? That is, could there be a prime $p$ such that $p^2$ divides $n$?
I'll try another solution, thanks.
â Bor
Feb 26 at 3:20
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
The most obvious improvement is to notice that if i in the_primes
and if val not in the_primes
both take $mathcalO(n)$ time. If you made the_primes
a set
instead of a list
it would only be $mathcalO(1)$. So just write:
the_primes = set(primes())
Also note that your "prime number generator" is not actually a Python generator. For that you would need to add a yield
:
def primes(ubound=10**5):
""" Generating prime numbers https://stackoverflow.com/a/8627193/1770460 """
size = (ubound - 3) // 2
a = [False] * size
s = 0
while s < size:
t = 2 * s
p = t + 3
yield p
for n in range(t * (s + 3) + 3, size, p):
a[n] = True
s = s + 1
while s < size and a[s]:
s = s + 1
The set()
call will then consume the generator. This will not make your code run faster, though (it needs about the same CPU) It might save you some memory, because you don't need the conversion from the internal list to the external set
.
Your original code takes about 43.5s on my machine. With the two changes in this post this drops down to less than 1.7s:
$ python3 -m cProfile 357.py
275
time elapsed 1.6228196620941162 sec.
583585 function calls in 1.623 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
...
9592 0.011 0.000 0.011 0.000 euler_357.py:14(primes)
1 0.001 0.001 1.623 1.623 euler_357.py:3(<module>)
1 1.524 1.524 1.584 1.584 euler_357.py:34(number_divisors)
1 0.026 0.026 0.026 0.026 euler_357.py:56(find_count)
...
alternatively, you could make your prime sieve add to a set rather than to a list and then convert to set.
â Oscar Smith
Feb 24 at 21:25
@OscarSmith Yeah, or make it a generator and consume it withset()
. Not much difference since the primes are all unique, of course. But it might save some memory since the internal datastructure is not needed.
â Graipher
Feb 24 at 21:27
Good idea about the sieve, it's an improvement.
â Bor
Feb 25 at 9:31
add a comment |Â
up vote
2
down vote
accepted
The most obvious improvement is to notice that if i in the_primes
and if val not in the_primes
both take $mathcalO(n)$ time. If you made the_primes
a set
instead of a list
it would only be $mathcalO(1)$. So just write:
the_primes = set(primes())
Also note that your "prime number generator" is not actually a Python generator. For that you would need to add a yield
:
def primes(ubound=10**5):
""" Generating prime numbers https://stackoverflow.com/a/8627193/1770460 """
size = (ubound - 3) // 2
a = [False] * size
s = 0
while s < size:
t = 2 * s
p = t + 3
yield p
for n in range(t * (s + 3) + 3, size, p):
a[n] = True
s = s + 1
while s < size and a[s]:
s = s + 1
The set()
call will then consume the generator. This will not make your code run faster, though (it needs about the same CPU) It might save you some memory, because you don't need the conversion from the internal list to the external set
.
Your original code takes about 43.5s on my machine. With the two changes in this post this drops down to less than 1.7s:
$ python3 -m cProfile 357.py
275
time elapsed 1.6228196620941162 sec.
583585 function calls in 1.623 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
...
9592 0.011 0.000 0.011 0.000 euler_357.py:14(primes)
1 0.001 0.001 1.623 1.623 euler_357.py:3(<module>)
1 1.524 1.524 1.584 1.584 euler_357.py:34(number_divisors)
1 0.026 0.026 0.026 0.026 euler_357.py:56(find_count)
...
alternatively, you could make your prime sieve add to a set rather than to a list and then convert to set.
â Oscar Smith
Feb 24 at 21:25
@OscarSmith Yeah, or make it a generator and consume it withset()
. Not much difference since the primes are all unique, of course. But it might save some memory since the internal datastructure is not needed.
â Graipher
Feb 24 at 21:27
Good idea about the sieve, it's an improvement.
â Bor
Feb 25 at 9:31
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
The most obvious improvement is to notice that if i in the_primes
and if val not in the_primes
both take $mathcalO(n)$ time. If you made the_primes
a set
instead of a list
it would only be $mathcalO(1)$. So just write:
the_primes = set(primes())
Also note that your "prime number generator" is not actually a Python generator. For that you would need to add a yield
:
def primes(ubound=10**5):
""" Generating prime numbers https://stackoverflow.com/a/8627193/1770460 """
size = (ubound - 3) // 2
a = [False] * size
s = 0
while s < size:
t = 2 * s
p = t + 3
yield p
for n in range(t * (s + 3) + 3, size, p):
a[n] = True
s = s + 1
while s < size and a[s]:
s = s + 1
The set()
call will then consume the generator. This will not make your code run faster, though (it needs about the same CPU) It might save you some memory, because you don't need the conversion from the internal list to the external set
.
Your original code takes about 43.5s on my machine. With the two changes in this post this drops down to less than 1.7s:
$ python3 -m cProfile 357.py
275
time elapsed 1.6228196620941162 sec.
583585 function calls in 1.623 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
...
9592 0.011 0.000 0.011 0.000 euler_357.py:14(primes)
1 0.001 0.001 1.623 1.623 euler_357.py:3(<module>)
1 1.524 1.524 1.584 1.584 euler_357.py:34(number_divisors)
1 0.026 0.026 0.026 0.026 euler_357.py:56(find_count)
...
The most obvious improvement is to notice that if i in the_primes
and if val not in the_primes
both take $mathcalO(n)$ time. If you made the_primes
a set
instead of a list
it would only be $mathcalO(1)$. So just write:
the_primes = set(primes())
Also note that your "prime number generator" is not actually a Python generator. For that you would need to add a yield
:
def primes(ubound=10**5):
""" Generating prime numbers https://stackoverflow.com/a/8627193/1770460 """
size = (ubound - 3) // 2
a = [False] * size
s = 0
while s < size:
t = 2 * s
p = t + 3
yield p
for n in range(t * (s + 3) + 3, size, p):
a[n] = True
s = s + 1
while s < size and a[s]:
s = s + 1
The set()
call will then consume the generator. This will not make your code run faster, though (it needs about the same CPU) It might save you some memory, because you don't need the conversion from the internal list to the external set
.
Your original code takes about 43.5s on my machine. With the two changes in this post this drops down to less than 1.7s:
$ python3 -m cProfile 357.py
275
time elapsed 1.6228196620941162 sec.
583585 function calls in 1.623 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
...
9592 0.011 0.000 0.011 0.000 euler_357.py:14(primes)
1 0.001 0.001 1.623 1.623 euler_357.py:3(<module>)
1 1.524 1.524 1.584 1.584 euler_357.py:34(number_divisors)
1 0.026 0.026 0.026 0.026 euler_357.py:56(find_count)
...
edited Feb 25 at 12:10
answered Feb 24 at 21:06
Graipher
20.5k43081
20.5k43081
alternatively, you could make your prime sieve add to a set rather than to a list and then convert to set.
â Oscar Smith
Feb 24 at 21:25
@OscarSmith Yeah, or make it a generator and consume it withset()
. Not much difference since the primes are all unique, of course. But it might save some memory since the internal datastructure is not needed.
â Graipher
Feb 24 at 21:27
Good idea about the sieve, it's an improvement.
â Bor
Feb 25 at 9:31
add a comment |Â
alternatively, you could make your prime sieve add to a set rather than to a list and then convert to set.
â Oscar Smith
Feb 24 at 21:25
@OscarSmith Yeah, or make it a generator and consume it withset()
. Not much difference since the primes are all unique, of course. But it might save some memory since the internal datastructure is not needed.
â Graipher
Feb 24 at 21:27
Good idea about the sieve, it's an improvement.
â Bor
Feb 25 at 9:31
alternatively, you could make your prime sieve add to a set rather than to a list and then convert to set.
â Oscar Smith
Feb 24 at 21:25
alternatively, you could make your prime sieve add to a set rather than to a list and then convert to set.
â Oscar Smith
Feb 24 at 21:25
@OscarSmith Yeah, or make it a generator and consume it with
set()
. Not much difference since the primes are all unique, of course. But it might save some memory since the internal datastructure is not needed.â Graipher
Feb 24 at 21:27
@OscarSmith Yeah, or make it a generator and consume it with
set()
. Not much difference since the primes are all unique, of course. But it might save some memory since the internal datastructure is not needed.â Graipher
Feb 24 at 21:27
Good idea about the sieve, it's an improvement.
â Bor
Feb 25 at 9:31
Good idea about the sieve, it's an improvement.
â Bor
Feb 25 at 9:31
add a comment |Â
up vote
1
down vote
It's worth doing a bit of mathematics before embarking on a brute-force search. In order not to spoil the problem, I'll give a couple of hints.
Hint 1
If $n$ satisfies the condition of the problem, then for every divisor $d$ of $n$, it must be the case that $d + nover d$ is prime. Are there any divisors of $n$ that you already know about (without having to factorize $n$)? What therefore can you conclude about $n$?
Hint 2
If $n$ satisfies the condition of the problem, can it be the case that $n$ has a repeated factor? That is, could there be a prime $p$ such that $p^2$ divides $n$?
I'll try another solution, thanks.
â Bor
Feb 26 at 3:20
add a comment |Â
up vote
1
down vote
It's worth doing a bit of mathematics before embarking on a brute-force search. In order not to spoil the problem, I'll give a couple of hints.
Hint 1
If $n$ satisfies the condition of the problem, then for every divisor $d$ of $n$, it must be the case that $d + nover d$ is prime. Are there any divisors of $n$ that you already know about (without having to factorize $n$)? What therefore can you conclude about $n$?
Hint 2
If $n$ satisfies the condition of the problem, can it be the case that $n$ has a repeated factor? That is, could there be a prime $p$ such that $p^2$ divides $n$?
I'll try another solution, thanks.
â Bor
Feb 26 at 3:20
add a comment |Â
up vote
1
down vote
up vote
1
down vote
It's worth doing a bit of mathematics before embarking on a brute-force search. In order not to spoil the problem, I'll give a couple of hints.
Hint 1
If $n$ satisfies the condition of the problem, then for every divisor $d$ of $n$, it must be the case that $d + nover d$ is prime. Are there any divisors of $n$ that you already know about (without having to factorize $n$)? What therefore can you conclude about $n$?
Hint 2
If $n$ satisfies the condition of the problem, can it be the case that $n$ has a repeated factor? That is, could there be a prime $p$ such that $p^2$ divides $n$?
It's worth doing a bit of mathematics before embarking on a brute-force search. In order not to spoil the problem, I'll give a couple of hints.
Hint 1
If $n$ satisfies the condition of the problem, then for every divisor $d$ of $n$, it must be the case that $d + nover d$ is prime. Are there any divisors of $n$ that you already know about (without having to factorize $n$)? What therefore can you conclude about $n$?
Hint 2
If $n$ satisfies the condition of the problem, can it be the case that $n$ has a repeated factor? That is, could there be a prime $p$ such that $p^2$ divides $n$?
answered Feb 25 at 14:17
Gareth Rees
41.1k394167
41.1k394167
I'll try another solution, thanks.
â Bor
Feb 26 at 3:20
add a comment |Â
I'll try another solution, thanks.
â Bor
Feb 26 at 3:20
I'll try another solution, thanks.
â Bor
Feb 26 at 3:20
I'll try another solution, thanks.
â Bor
Feb 26 at 3:20
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f188279%2fproject-euler-357-prime-number-generator-in-python-3%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
I do not remember solving this issue so I do not have an algorithmic truck for that one. It won't make a huge difference but you'd benefit from using divmod to have both quotient and remainder....
â Josay
Feb 24 at 17:38
1
1 is a factor of all numbers. Hence, you will be testing (1 + n/1) for primality. Consider what happens if n is odd and > 1? There are further simplifications possible, but this is the most obvious.
â rossum
Mar 2 at 12:39