Java Prime Checker

если найдена первая проверка в java, которая использует этот метод. Может кто-нибудь объяснить, почему for-loop переходит к квадратному корню из искомого простого числа? - Есть ли более эффективный способ сделать это? - Спасибо!Java Prime Checker

public static boolean isPrime(int p){ 
      if(p % 2 == 0 || p < 2){ 
       return false; 
      } 
      else { 
       System.out.println("Sqare: " + (int)Math.sqrt(p)); 
       for(int i = 3; i <= (int)Math.sqrt(p); i = i+2){ 
        if(p % i == 0){ 
         return false; 
        } 
       } 
      } 

      return true; 
}

источник

2016-12-11 JSt

Возможный дубликат [Почему мы проверяем квадратный корень простого числа, чтобы определить, является ли оно простым?] (Http://stackoverflow.com/questions/5811151/why-do-we-check-up -to-the-square-root-of-a-prime-number-to-define-if-it-is-pr) – rafid059

Кроме того, проверьте их: http://stackoverflow.com/questions/1801391/what- is-the-best-algorithm-for-check-if-a-number-is-prime http://stackoverflow.com/questions/453793/which-is-the-fastest-algorithm-to-find-prime-numbers – rafid059

Попробуйте высушить код, если хотите понять код. Возьмите разные цифры и попробуйте запустить их. Или попробуйте отладить среду. –

Если число не простое, то он имеет по крайней мере два фактора: 63 = 7 х 9 или 121 = 11 х 11, например. Меньший из двух факторов должен быть меньше или равен квадратному корню из исходного числа. Если вы обнаружите какой-либо фактор, то число не является простым, поэтому вы можете остановить поиск, как только найдете первый фактор.

При поиске до квадратного корня и без него вы можете найти коэффициент составного числа. Если поиск достигает квадратного корня без нахождения фактора, то число должно быть простым с коэффициентами 1 и самим номером. Нет необходимости вести поиск за пределами квадратного корня, так как вы не узнаете ничего нового и будете тратить время.

источник

2016-12-11 19:35:57 rossum

ответ

Смежные вопросы