PY
py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
'''
Project Euler, Problem 864
Let C(n) be the number of squarefree integers of the form x^2 + 1 such that 1 <= x <= n.
For example, C(10) = 9 and C(1000) = 895.
Find C(123567101113).
'''
from sympy import primerange
import numpy as np
def get_squared_primes(n):
return np.fromiter(primerange(2,n),int)**2
def square_free(n):
nums = np.arange(1,n+1)**2+1
psqrt = get_squared_primes(n)
for i in np.nditer(psqrt):
nums = nums[nums%i!=0]
return nums.size
#n = 123567101113
n = 1000
print(f'''n = {n}
C({n}) = {square_free(n)}''')
Enter to Rename, Shift+Enter to Preview
OUTPUT
Run