Sage (Python) Математическое программирование, Написание алгоритма для проверки на простоту

Мне нужно написать код в Sage для домашней задачи, которая проверяет, является ли случайное число, сгенерированное между 10 ^ 7 и 10 ^ 8, простым, путем деления его на все известные простые числа, меньшие или равные 10 ^ 4. Я никогда не программировал в Sage до этого в качестве предупреждения. Это то, что у меня есть до сих пор.

# This creates a function to create a random number between two numbers

def random_between(j,k):
    a=int(random()*(k-j+1))+j
    return a

# Testing that the function works, which it does, though I don't know how
# to assign a variable to it like x=random_between(10^7,10^8)

random_between(10^7,10^8)

# The list of primes less than 10^4 is given by

list_of_primes = prime_range(1,10^4)

# Want to write a function to check if prime
def check_if_prime(n):
    for n in list_of_primes:
        if n % random_between(10^7,10^8)==0:
            print 'number is prime'
        else
            print 'number is not prime'

Что я хочу сделать, так это определить, делят ли числа в list_of_primes случайное число, сгенерированное из random_between с помощью команды %, а затем напечатать это number x is a prime или нет.

Я знаю, что команда Primes() будет проверять, является ли число простым или нет, но мы специально должны делать эту «наивную» проверку простоты. Если бы кто-то мог помочь мне с этим, я был бы очень признателен.


python primes sage number-theory
person Cori Vander Werf    schedule 01.07.2016    source источник
comment
Учитывая n < 10^4 и 10^7 <= random_x < 10^8, тогда n % random_x всегда будет n, потому что n < random_x. Я думаю, вы имели в виду x = random_between(10**7, 10**8); if x % n == 0: ...   -  person AChampion    schedule 01.07.2016

Ответы (1)


arrow_upward
0
arrow_downward

Ваша функция check_if_prime может потребовать некоторой работы. Я переписал ниже.

def check_if_prime(): # there's no parameter for this method since we're checking against the global var list_of_primes
    for n in list_of_primes:
        if random_between(10^7,10^8) % n == 0: # if a random number / a prime number has no remainder, the random number is not prime
            print 'number is not prime'
            return # we're done, we know it's not prime
    print 'number is prime' # we made it through all of our tests, the number might be prime
person nlloyd    schedule 01.07.2016