Weekly Challenges
Solve the challenge, share your solution and summit the ranks of our Community!Also available in | Français | Português | Español | 日本語
IDEAS WANTED
Want to get involved? We're always looking for ideas and content for Weekly Challenges.
SUBMIT YOUR IDEA
Managed to make an app that will work for any number between 1 and 10,000 (8 seconds to run though). If there are two prime numbers which are equal distance from your number then it will return both (e.g. 9 is equidistant from 7 and 11) and if your number is prime it will tell you.
I decided to use Python to solve this challenge, since it was the simplest way for me to solve.
from ayx import Alteryx
# Import pandas to write data out
import pandas as pd
# Import math for the infinity functionality
import math
myinput = Alteryx.read("#1")
numbercheck = myinput['Number'].iloc[0]
# The Sieve of Eratosthenes method of calculating the primes less than the limit
def getPrimes(limit):
# The list of prime numbers
primes = []
# The boolean list of whether a number is prime
numbers = [True] * limit
# Loop all of the numbers in numbers starting from 2
for i in range(2, limit):
# If the number is prime
if numbers[i]:
# Add it onto the list of prime numbers
primes.append(i)
# Loop over all of the other factors in the list
for n in range(i ** 2, limit, i):
# Make them not prime
numbers[n] = False
# Return the list of prime numbers
return primes
# The number to find the closest prime of
number = int(numbercheck)
# The list of primes using the function declared above
primes = getPrimes(number + 100)
# The distance away from the closest prime
maxDist = math.inf
# The closest prime
numb = 0
# Loop all of the primes
for p in primes:
# If the prime number is closer than maxDist
if abs(number - p) < maxDist:
# Set maxDist to the number
maxDist = abs(number - p)
# Set numb to the number
numb = p
# Create data frame for output
df = pd.DataFrame(
{"Number" : [numbercheck],
"Closest Prime Number" : [numb]})
Alteryx.write(df,1)
Cheers!
Phil
I learn a important lesion here,
use MORE tool to save MORE time
At the beginning, I try up to 1,000,000. by brute force. (i.e. generate factor from 1 to 1,000,020)
It take 44 second.
By adding one filter tool to filter out the first 5 prime number factors (i.e 2, 3, 5, 7, 9), time reduce to 19 seconds.
By change the formula, brute force to Square Root of 1,000,020 (i.e. 1001). time reduce to 1 second.
it is important to learn to the logic and add right tool. It keys to reduce processing time.
why use square root,
square root use to cut half of the factor since it duplicate. it save significant amount of time when the number is high.
example: for number 10, factor is 1, 2, 5 and 10.
when 1 and 2 (A), it already consist of factor 5 and 10 (B), hence need not to go further.
