Is there a way to remove elements of a range without creating an array/list of included/excluded val-CodePudding

I am using Python 3.9 and I have created a very simple program to identify whether or not a number is prime when given in integer input. My code itself works, but it can be very slow even given large numbers (50 million ). I am using a for loop to check if any numbers between 1 and the input(x) are evenly divisible by the input(x). I want to exclude all even numbers and multiples of 5 from the range since no primes are even or end in 5.

Is there a way to explicitly remove all evens and multiples of 5 without creating an array of excluded/included values like I did? Here is a snippet code and time of the program for reference:

#program without filtering out evens and multiples of 5
print("Is your number prime?? Well... let's check!")
#'x' can actually be any input but I am using 60000049 as a constant value for the sake of timing.
x=60000049
factorlist=[]
#Included_values is an array in which all elements are divided into 'x' after it excluded all evens and multiples of 5.
included_values=[]
for i in range (1,x 1):
    if i%2!=0 or i%5!=0:
        included_values.append(i)
for i in range(1,len(included_values)):
    if x%included_values[i]==0:
        factorlist.append(i)
if len(factorlist)>2:
    print("Oh no! It appears like the number you have entered is not prime. Try again!")
    print('The factors to your number are:',factorlist)
if len(factorlist)<=2:
    print('Yay! You have chosen a prime number!!')
Yay! You have chosen a prime number!!
~17.96522307395935

The first version of my program is much slower than the one that does not exclude any values:

#My program without filtering out evens or multiples of 5.
#'x' can actually be any number but I am using 60000049 for the sake of timing.
print("Is your number prime?? Well... let's check!")
x=60000049
factorlist=[]
for i in range (1,x 1):
    if x%i==0:
        factorlist.append(i)
if len(factorlist)>2:
    print("Oh no! It appears like the number you have entered is not prime. Try again!")
    print('The factors to your number are:',factorlist)
if len(factorlist)==2:
    print('Yay! You have chosen a prime number!!')
Yay! You have chosen a prime number!!
~6.147368431091309

As you can see, my second program is much faster because it does not cycle through the range to get an array of excluded values first. If there is a way to exclude even values and multiples of 5 first without cycling through the entire range (1,x 1), it would make my program much faster. If this is possible, let me know!

CodePudding user response：

To answer your question, you could of course have an if inside the for to skip values. Well you already do, but using a list. I mean you could just have condition there.

Otherwise, a list comprehension is a more efficient way to create a new list than calling append in a loop like you do:

included_values = [i for i in range(1, x 1)
                   if i%2 !=0 or i%5 != 0]

I did that change in https://replit.com/@ToniAlatalo/DapperSeagreenMacro#main.py

Also the other for I think you could convert from:

for i in range(1,len(included_values)):

to:

for value in included_values:

Which might be a tiny bit faster but probably not much different.

CodePudding user response：

If you want to exclude multiples of 2 or 5 only, you can try using list comprehension included_values = [k for k in range(1,x 1) if k%2!=0 and k%5!=0]

If you want your program to be "more efficient", I suggest checking to the square root of x only. included_values = [k for k in range(1, math.ceil(math.sqrt(x)))]

But, your code is not that efficient.

x = int(input("Is your number prime?? Well... let's check! Type your number here:" ))
from math import sqrt, ceil
if x ==2:
    print('Your number is a prime')
elif x < 2:
    print("Your number isn't prime")
else:
    print('Your number is not prime' if any([k for k in range(2,ceil(sqrt(x))) if x%k==0]) else 'Your number is a prime')

Breakdown of code:

x = int(input("Is your number prime?? Well... let's check! Type your number here:" )) This will get your "x", but if x is predetermined, you can skip this.

from math import sqrt,ceil This will import sqrt and ceil from the math library

if x ==2:
    print('Your number is a prime')
elif x < 2:
    print("Your number isn't prime")

Check if number is smaller than 3, if it's 2, print the number is prime, else print that it's not prime

print('Your number is not prime' if any([k for k in range(1,ceil(sqrt(x))) if x%k==0]) else 'Your number is a prime') Check if any([k for k in range(2,ceil(sqrt(x))) if x%k==0]) is true, if it's true, number isn't a prime, but if it's false, number is a prime(Since x isn't divisible by any number in range of 2 to square root of x).

Granted, this is not perfect but will be fast enough for normal uses.