代码之家  ›  专栏  ›  技术社区  ›  Kriton Georgiou

素数查找器

  •  -3
  • Kriton Georgiou  · 技术社区  · 9 年前

    因此,我正在尝试使用acm中的RandomGenerator类来创建一个方法,该方法可以找到从0到n(由用户输入)的随机素数。utils包,因为某些原因它不起作用!我想了很多次,我认为这个解决方案是正确的,但它最终给出的数字并没有错!

    这是大学的一个项目,我只能使用acm。实用程序!没有扫描仪!只有这种代码

    public int nextPrime(int n){
        int num = rgen.nextInt(1, n);   
        boolean prime=false;
        if (num==1){
            return (num);
        }else{
            int i = 2;
            int c = 0;
            while ((i < num-1)&&(prime=false)){
                if( (num % i) == 0){
                    c=c+1;
                }
                if((c==0)&&(i==(num-1))){
                    prime=true;
                }
                if(c>=1){
                    num = rgen.nextInt(1, n);
                    i=1;
                }
            i=i+1;
            }
        }
        return (num);
        }
    
    4 回复  |  直到 9 年前
        1
  •  1
  •   RockAndRoll    9 年前

    = 用于分配和 == 用于比较。 你需要改变你的状况

    while ((i < num-1)&&(prime=false)){
    

     while ((i < num-1)&&(prime==false)){ or
     while ((i < num-1)&&(!prime)){
    
        2
  •  1
  •   K.D. Code    9 年前

    这里有一个确定数字是否为素数的基本方法。这个方法实际上只是为了理解发现一个数是否为素数背后的逻辑。享受

    public boolean isPrime()
    {
    boolean prime = true;
    
        for (int s = 2; s < original; s++)
        if (original % s != 0 )
        {
            prime = true;
    
        }
        else
        {
            prime = false;
            return prime;
        }
    
        return prime;
    
        3
  •  0
  •   guillaume girod-vitouchkina    9 年前

    你的代码相当 奇怪的 .像c这样的变量不太清楚,名称也无济于事。

    您可以阅读其他实现。

    我做了一些改变,使之有效。痕迹也有帮助!

    public static int nextPrime(int n)
        {
        int num = (int)(1+Math.random()*n);  // other generator
    
     // TRACE HERE
        System.out.println("START:"+num);
    
        boolean prime=false;
    
        // CHANGE HERE
        if (num==2)
            {
            return (num);
            }   
            else
            {
            int i = 2;
            int c = 0;
    
            // CHANGE HERE
            while ((i < num-1)&&(prime==false))
                {
                // Not prime => next one
                if( (num % i) == 0)
                    {
                    // TRACE HERE
                    System.out.println("YOU LOSE: :"+num+" divided by "+i);
    
                    c=c+1;
                    } 
    
                if((c==0)&&(i==(num-1)))
                    {
                    prime=true;
    
                    // TRACE HERE
                    System.out.println("BINGO:"+num);
    
                    // CHANGE HERE
                    break;
                    }
    
                if(c>=1)
                    {
                    // SAME PLAYER LOOP AGAIN
                    num = (int)(1+Math.random()*n);
    
                    // TRACE HERE
                    System.out.println("RESTART:"+num);
    
                    i=1;
    
                    // CHANGE HERE
                    c=0;
                    }
            i=i+1;
            }
        }
        return (num);
        }
    
        4
  •  0
  •   Douglas Zare    9 年前

    要么你错报了问题,要么你没有接近正确编码问题。有4个素数直到10:{2,3,5,7}。如果用户输入10,你应该从这个集合中给出一个随机素数,还是前10个素数{2,3,5,7,11,13,17,19,23,29}中的随机素数?你说问题出在第一种解释上(11不是对10的有效回应),但你尝试了第二种解释(11是对10的正确回应)。

    有一种简单的方法可以在[100000]范围内的素数内均匀地生成素数。在范围内选择一个随机整数,并测试它是否为素数。如果是,请将其退回。如果没有,请重复。这称为拒绝抽样。在没有拒绝抽样的情况下,要得到一个均匀随机的素数是相当复杂的,因为在大范围内计数或列出素数并不容易。测试一个数是否为素数相对容易,对于n>1平均只需要大约logn个样本就可以找到[1,n]中的素数。