时间戳

首页 > 解决方案 > 无法理解数字是否为素数的测试背后的逻辑

java - 无法理解数字是否为素数的测试背后的逻辑

问题描述

/**
 * The isPrime method iterates through every number in the range of 1 - 100 and adds every prime number to a 
   list in the file created by the user
 * @param filename The file that numbers will be added to
 */

public static void isPrime(String filename) throws IOException
{
   boolean status = true;          // tells method if number is prime or not (if status = true, number is prime)

   // opens up previously-created file for writing
   FileWriter fwriter = new FileWriter(filename, true);
   PrintWriter outputFile = new PrintWriter(fwriter);

   for (int i = 1; i <= 100; i++)
   {
       // check if each number is prime 
        status = checkPrime(i);

        if (status == true && i != 1)
        {
            outputFile.println(i);
        }
   }

   outputFile.close();
}

/**
 * The checkPrime method tests each number passed in as a parameter to see if it is prime
 * @param num Integer to be tested
 * @return Returns a boolean value of either true or false
 */

public static boolean checkPrime(int num)
{
    int remainder;              // used to test whether number is prime or not

    for (int j = 2; j < num; j++)
    {
        remainder = num % j;
        if (remainder == 0)
        {
            return false;
        }
    }
    return true;
}

这是我作业的一部分。代码运行，但我需要帮助的是理解为什么第二种方法 checkPrime() 有效的逻辑。我意识到这可能很明显，但我是一名新的 cs 学生，所以如果有人愿意解释为什么这对我有用，我将不胜感激。

标签： java

解决方案

% 运算符是余数运算符。它从 2 开始迭代，num以查看素数是否可以被这些数字中的任何一个整除。一旦它是，它就不能是素数，所以它返回 false。如果完成且没有除数，则返回 true。

但是有一种更有效的方法。仅将候选数除以num不2超过 的平方根的值num。想想看，如果到那一点没有余数，那么从 to 的平方根中没有其他数字num 会num除它。

所以首先检查 的可分性2。然后从3奇数开始。

所以方法看起来像这样。

public static boolean checkPrime(int num)
{
    int remainder;              // used to test whether number is prime or not
    if(num % 2 == 0) {
         return false;
    }          
    for (int j = 3; j < (int)Math.sqrt(num)+1; j+=2)
    {
        remainder = num % j;
        if (remainder == 0)
        {
            return false;
        }
    }
    return true;
}

推荐阅读