1

我正在尝试更熟悉Java，所以尝试我自己的逻辑来解决以下问题打印前100个正整数中存在的所有素数......

import java.io.IOException;

class PrimeNumbers{
    public static void main(String[] args) throws IOException
    {
        int[] num=new int[101];   //array to store values from 1 to 100
        int[] prime=new int[50];   //array to store prime numbers

        for(int i=1;i<=100;i++) 
            num[i]=i;     //add values from 1 to 100 to "num" array

        int i=1;      //index for "num" array
        int j=0;      //index for "prime" array
        int chk;      //temporary variable to store value from "num" to carry out all "checking operations"

        while(i<=100)
        {
            chk=num[i];
            if(chk==1)
            {
                prime[j++]=chk;
                i++;
                break;
            }
            else if(chk==2)
            {
                i++;
                break;
            }
            else if(chk==3)
            {
                prime[j++]=chk;  //increment i and j after adding the "chk" value to "prime" array 
                i++;
                break;
            }
            else if((chk % 2)!=0 && (chk % 3)!=0)   //if number is divisible by 2 or 3,no need to check further
            { 
                int k=4; 

                while(k<((chk+1)/2))   //check if value of "k" is less than half of "chk" value
                {
                    if(chk%k!=0) k++;   //increment "k" from 4 to half of chk's value and check if any of them is divisible
                }

                prime[j++]=chk;    
                i++;
                break;
            }   
            else
            i++;
        }
        for(int n=0;n<prime.length;n++)
            System.out.print(prime[n]+" "); //print the output
    }
}

问题是我没有收到任何错误，但输出不是我所期望的，我已经尝试了 3 个多小时来解决这个问题，但没有运气..

任何帮助将不胜感激，谢谢！

输出： 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

编辑：具有类似逻辑的更正版本

import java.io.IOException;



class PrimeNumbers{
    public static void main(String[] args) throws IOException
    {
        int[] prime=new int[50];   //array to store prime numbers
        int i=1;     
        int j=0;      //index for "prime" array
        int chk;      //temporary variable to store value i to carry out all "checking operations"

        while(i<=100)
        {
            chk=i;
            if(chk==1)
            {
                i++;
            }
            else if(chk==2)
            {
                prime[j++]=chk;  //increment i and j after adding the "chk" value to "prime" array 
                i++;
            }
            else if(chk==3)
            {
                prime[j++]=chk;  //increment i and j after adding the "chk" value to "prime" array 
                i++;
            }
            else if((chk % 2)!=0 && (chk % 3)!=0)   //if number is divisible by 2 or 3,no need to check further
            { 
                int k=5;
                boolean flag=false;
                while(k<(chk/2) && k<50)   //check if value of "k" is less than half of "chk" value
                {
                    if(chk%k!=0)
                    {
                        k++;         //increment "k" from 4 to half of chk's value and check if any of them is divisible
                    }
                    else 
                    {
                        flag=true;
                        break;
                    }
                }
                if(!flag)
                {
                 prime[j++]=chk;
                }
                i++;
            }   
            else
            {
            i++;
            }
        }
        for(int n=0;n<prime.length;n++)
            if(prime[n]!=0)
            System.out.print(prime[n]+" "); //print the output
    }
}

输出： 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

4

7 回答 7

3

break块内的语句if将打破while循环。因此，删除循环break内的所有语句。while

于 2013-10-23T10:23:26.700 回答
1

从 if 块中删除break，因为 Break 语句完成了 while 循环的执行

追踪i=0,

while(i<=100)
{
   chk=num[i]; // In num array num[i] = i, as assigned by you, so chk =1
   if(chk==1)   //chk==1 is true
   {
      prime[j++]=chk;  // j++ = 0 and then ++ ,so prime[0] = 1
      i++;
      break; // here your execution of while block finishes because of break
   }
   else if(chk==2){
      i++;
      break;
   }
.............
}

而在 for 循环中的第一个值 ieprime[0] is 1除外all values in prime is zero。

for(int n=0;n<prime.length;n++)
        System.out.print(prime[n]+" "); // prime[0] = 1 & all other is zero.

这就是为什么你得到如此荒谬的输出

Use continue & not break
于 2013-10-23T10:38:42.880 回答
1

当您将 1 放入素数列表时，您会跳出循环：

    if(chk==1)
    {
        prime[j++]=chk;
        i++;
        break;
    }

删除那个（其他类似的）中断。

于 2013-10-23T10:26:57.900 回答
1

你的休息；声明是问题。 

else if((chk % 2)!=0 && (chk % 3)!=0)   //if number is divisible by 2 or 3,no need to check further
{ 
    int k=4; 

    while(k<((chk+1)/2))   //check if value of "k" is less than half of "chk" value
    {
        if(chk%k!=0) k++;   //increment "k" from 4 to half of chk's value and check if any of them is divisible
     }
     prime[j++]=chk;    
     i++;
     break;  //here is the problem. you are breaking the outer loop
 }
于 2013-10-23T10:27:05.687 回答
1

你不需要数组。有一个更简单的方法。

运行一个数字 (x) 循环，并在其中另一个循环从 2 到 x (y) 的一半。如果 x 可以被 y 整除，则它不是素数。

于 2013-10-23T10:27:57.140 回答
1

您的程序根本没有实现主要算法。

除了您将 1 视为素数而不是 2 的事实之外，您的代码的核心是：

else if( something irrelevant ) { 
    int k=4;

    while( something ) {
        if(chk%k!=0) k++; 
    }

    prime[j++]=chk;    
    i++;
    break;
}

只是指出两个严重的问题，而不注意其他问题：

您会竭尽全力k在 while 循环中进行计算。这个 while 循环可能永远不会终止，即 when chk%k == 0。但是，在冒着你的程序永远运行的风险之后，你甚至不使用k! 相反，您只需将其包含chk为质数。这显然是错误的。

于 2013-10-23T10:43:52.813 回答
1

  1. 首先删除中断，它们使您退出 while 循环并删除对 1 的检查（根据主流，它既不是素数也不是复合数）

  2. 为了简化您的逻辑，您需要检查该数字是否可被 2 个数字整除[逻辑：素数可被 1 和自身整除] 如果是这样，您可以跳过该数字作为非素数并继续下一个。所以你的内在 else if 条件 " else if((chk % 2)!=0 && (chk % 3)!=0)" 变成

    else if((chk % 2)!=0 && (chk % 3)!=0)

    {

            int k=4;
        int flag=1;
        while((k<((chk+1)/2)))   //check if value of "k" is less than half of "chk" value
        {
            if(chk%k==0)
                flag++;
            k++;   //increment "k" from 4 to half of chk's value and check if any of them is divisible
        }
        if(flag<2)
            prime[j++]=chk;    
        i++;

    // break;
    }

3.想想这个逻辑
所有能被2整除的数字都不是素数所以如果一个数字不能被一个素数整除那么你可以将你的数字增加2
然后它是一个素数
试试这个代码

public static void main(String[] args) throws IOException
    {
        int[] prime=new int[50];   //array to store prime numbers within 1-n prime numbers will be <=n/2
        int i=1;        //index for "num" array
        int j=1;        //index for storing to "prime" array
        int k=1;        //index for browsing through prime array
        prime[0]=2;     // setting the first element
        int flag=1;     // to check if a number is divisibe for than 2 times
        for(i=3;i<=100;i+=2) {
            for(k=0;prime[k]!=0;k++)    //browsing through the array to till non zero number is encountered
            {
                if(i%prime[k]==0) flag++;   //checking if the number is divisible, if so the flag is incremented 
            }
            if(flag<2)
            {
                prime[j++]=i;               // if the flag is still 1 then the number is a prime number
            }
            flag=1;
        }
        System.out.println(Arrays.toString(prime)); //a short way to print an array
        }
于 2013-10-23T13:57:52.150 回答