Каков наилучший алгоритм проверки, является ли число простым? - PullRequest
Новая
       70

Каков наилучший алгоритм проверки, является ли число простым?

144 голосов
/ 26 ноября 2009

Просто пример того, что я ищу: я мог бы представить каждое нечетное число с битом, например, для данного диапазона чисел (1, 10], начинается с 3: 

1110

Следующий словарь можно сжать более правильно? Я мог бы определить кратные пять с некоторой работой, но числа, заканчивающиеся на 1, 3, 7 или 9, должны быть там в массиве битов. Надеюсь, это прояснит, чего я хочу.

Я ищу лучший алгоритм, чтобы проверить, простое ли число, то есть булева функция: 

bool isprime(number);

Я хотел бы знать лучший алгоритм для реализации этой функциональности. Естественно, была бы структура данных, которую я мог бы запросить. I определяет наилучший алгоритм , который представляет собой алгоритм, который создает структуру данных с самым низким потреблением памяти для диапазона (1, N], где N - константа.

Ответы [ 27 ]

0 голосов
/ 26 октября 2018

Мы можем использовать потоки Java для реализации этого в O (sqrt (n)); Учтите, что noneMatch - это метод shortCircuiting, который останавливает операцию, когда считает ее ненужной для определения результата: 

Scanner in = new Scanner(System.in);
int n = in.nextInt();
System.out.println(n == 2 ? "Prime" : IntStream.rangeClosed(2, ((int)(Math.sqrt(n)) + 1)).noneMatch(a -> n % a == 0) ? "Prime" : "Not Prime");
0 голосов
/ 26 октября 2018

Большинство предыдущих ответов верны, но вот еще один способ проверить, является ли число простым числом. Напомним, что простые числа - это целые числа, превышающие 1, чьи единственные коэффициенты равны 1 и самому себе ( source )

Решение:

Как правило, вы можете построить цикл и начать тестирование своего числа, чтобы увидеть, делится ли оно на 1,2,3 ... до числа, которое вы тестируете ... и т. Д., Но чтобы сократить время на проверку, вы можете разделить ваше число наполовину от значения вашего числа, потому что число не может быть точно делится на что-либо, превышающее половину его значения. Например, если вы хотите, чтобы 100 было простым числом, вы можете перебрать до 50.

Фактический код : 

def find_prime(number):
    if(number ==1):
        return False
    # we are dividiing and rounding and then adding the remainder to increment !
    # to cover not fully divisible value to go up forexample 23 becomes 11
    stop=number//2+number%2
    #loop through up to the half of the values
    for item in range(2,stop):
        if number%item==0:
           return False
        print(number)
    return True


if(find_prime(3)):
    print("it's a prime number !!")
else:
    print("it's not a prime")
0 голосов
/ 30 сентября 2018

Вы можете попробовать что-то вроде этого. 

def main():
    try:
        user_in = int(input("Enter a number to determine whether the number is prime or not: "))
    except ValueError:
        print()
        print("You must enter a number!")
        print()
        return
    list_range = list(range(2,user_in+1))
    divisor_list = []
    for number in list_range:
        if user_in%number==0:
            divisor_list.append(number)
    if len(divisor_list) < 2:
        print(user_in, "is a prime number!")
        return
    else:
        print(user_in, "is not a prime number!")
        return
main()
0 голосов
/ 14 августа 2017

Подобная идея алгоритму AKS, который был упомянут 

public static boolean isPrime(int n) {

    if(n == 2 || n == 3) return true;
    if((n & 1 ) == 0 || n % 3 == 0) return false;
    int limit = (int)Math.sqrt(n) + 1;
    for(int i = 5, w = 2; i <= limit; i += w, w = 6 - w) {
        if(n % i == 0) return false;
        numChecks++;
    }
    return true;
}
0 голосов
/ 23 марта 2018

Чтобы узнать, является ли число или числа в диапазоне простыми. 

#!usr/bin/python3

def prime_check(*args):
    for arg in args:
        if arg > 1:     # prime numbers are greater than 1
            for i in range(2,arg):   # check for factors
                if(arg % i) == 0:
                    print(arg,"is not Prime")
                    print(i,"times",arg//i,"is",arg)
                    break
            else:
                print(arg,"is Prime")

            # if input number is less than
            # or equal to 1, it is not prime
        else:
            print(arg,"is not Prime")
    return

# Calling Now
prime_check(*list(range(101)))  # This will check all the numbers in range 0 to 100 
prime_check(#anynumber)         # Put any number while calling it will check.
0 голосов
/ 19 апреля 2018 
public static boolean isPrime(int number) {
 if(number < 2)
   return false;
 else if(number == 2 || number == 3)
        return true;
      else {
        for(int i=2;i<=number/2;i++)
           if(number%i == 0)
             return false;
           else if(i==number/2)
                return true;
      }
    return false;
}
0 голосов
/ 27 марта 2018 
myInp=int(input("Enter a number: "))
if myInp==1:
    print("The number {} is neither a prime not composite no".format(myInp))
elif myInp>1:
    for i in range(2,myInp//2+1):
        if myInp%i==0:
            print("The Number {} is not a prime no".format(myInp))
            print("Because",i,"times",myInp//i,"is",myInp)
            break
    else:
        print("The Number {} is a prime no".format(myInp))
else:
    print("Alas the no {} is a not a prime no".format(myInp))
Страница:
...