Проверка простоты грубой силы для 16-битного целого числа - PullRequest
Новая
       22

Проверка простоты грубой силы для 16-битного целого числа

0 голосов
/ 05 марта 2019

Как я могу использовать грубую силу (наивный алгоритм), чтобы проверить, простое ли целое число 16 бит или нет, и распечатать все простые числа перед ним.пример номера: 1254786951475276. Это мой код: 

   import java.io.*;

public class PrimeNumbers {

    public static boolean checkPrime(long n)
    {
        if (n % 2 == 0)
            return false;

        for (int i = 3; i <= Math.sqrt(n); i += 2) 
        {
            if (n % i == 0)
                return false;
        }

        return true;
    }

    public static void generatePrimeNumbers(long n) {

        for (int i = 2; i<= n-1 ; i++) {

            if (checkPrime(i)) {
                System.out.println(i);
            }
        }
    }

    public static void main(String args[]) throws Exception{

        BufferedReader br = new BufferedReader (new InputStreamReader(System.in));

        long n = 0;
        n = Integer.parseInt(br.readLine());

        generatePrimeNumbers(n);
    }
    }

1 Ответ

0 голосов
/ 05 марта 2019

Полагаю, вы имеете в виду 16 цифр, а не 16 бит.16 бит действительно легко, и вы можете просто проверить это с помощью простого цикла и деления.Ваш checkPrime() может быть оптимизирован следующим образом: 

public static boolean checkPrime(long n)
{
    if (n == 2)
        return true;

    if (n % 2 == 0)
        return false;

    for (long i = 3; i <= Math.sqrt(n); i += 2) 
    {
        if (n % i == 0)
            return false;
    }

    return true;
}

Но если число становится слишком большим (я думаю, что даже для 16 цифр это не понадобится), вы можете использовать примитивность Миллера-Робинатест .Этот тест можно использовать для проверки, является ли число ОЧЕНЬ БОЛЬШОЙ простым или нет.

Если вам нужно сгенерировать все простые числа до определенного числа , вы можетеиспользуйте Сито Эратосфена .

Просто помните, что диапазон int составляет от -2,147,483,648 до 2,147,483,647, поэтому он не может содержать 16-значное число.Вы можете использовать long, поскольку его диапазон составляет от -9,223,372,036,854,775,808 до 9,223,372,036,854,775,807, поэтому он может содержать 16-значный номер.

...