Самый быстрый способ определить, является ли число простым числом или нет VB - PullRequest
Новая
       25

Самый быстрый способ определить, является ли число простым числом или нет VB

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

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

Code1: 

    Dim ch As String
    ch = "y"

    While ch = "y"

        If (num Mod 2 = 0)  Then
            Console.WriteLine("Is not a prime number!")
        Else
            Console.WriteLine("Is a prime number!")
        End If

Code2: check = 1 ', запускающий контрольную точку для использования ее в программе для определения простого числа 

    Dim Value As Long
    Console.Write(vbLf & "Enter a number To check Whater it is Prime or Not :")
    Value = Long.Parse(Console.ReadLine())
    start_time = Now
    Dim ch As ULong
    ch = 0
    Dim i As ULong
    i = 2
    While (i <= Value / 2)

        If (Value Mod i = 0) Then

            ch = 1
            Exit While

        End If

        i = i + 1

    End While
    If (ch = 0) Then
        Console.WriteLine("Prime Number")
    Else
        Console.WriteLine("Not Prime Number")
    End If

1 Ответ

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

Есть очень много главных тестеров, многие из них на этом сайте. Для проверки одного номера я использую более быстрый вариант вашего Code2 с небольшой дополнительной проверкой. Вот псевдокод: 

boolean function isPrime(num)

  //1, 0 and negatives cannot be prime.
  if (num < 2) then
    return false
  endif

  // 2 is the only even prime.
  if (num MOD 2 = 0) then
    return (num = 2)
  endif

  // Check for odd factors.
  limit <- sqrt(num)
  for (factor <- 3; factor <= limit; factor <- factor + 2) do
    if (num MOD factor = 0) then
      return false
    endif
  endfor

  // If we reach this point then the number is prime.
  return true

endfunction

Как сказал @ user448810, вы должны использовать квадратный корень целевого числа в качестве предела цикла тестирования. В основном вы можете вдвое сократить количество тестов, обрабатывая четные числа отдельно. После того, как вы вычли четные числа, вам нужно только проверить нечетные коэффициенты: 3, 5, 7, ...

...