计算素数最多N个整数 [英] Computing prime numbers up to N integers

问题描述

我试图写一个小脚本自己计算所有质数为n个（一个用户提交的参数），并将AP preciate的一点点帮助。我想使用的ArrayList写这个功能，并希望使其尽可能高效 - 再大的事情对我来说，我似乎无法把握正在做的一切，是标准的，最好的做法（即有类以大写字母等），所以如果你不介意，请指出，在这方面的任何错误，这样我就可以解决这些问题。

下面是code我写到目前为止，但我知道有优化它的许多方面 - 特别是，我有一个布尔数组存储数是否是素数或不。当然，有这样做比通过数组循环，使一切素数，则摆脱不属于数字的更好的办法？

非常感谢您的时间！ ：）

（TL;博士 - 编写一个脚本来计算机素数高达N.我想使用的ArrayList做到这一点，我怎样才能让我的code更好 - 特别是低效率的布尔数组）。

 进口的java.util。*;
公共类总理{

  公共静态无效的主要（字串[] args）{

  }
  公共静态无效的主要（INT参数：initialCapacity）{
    INT索引= 0;
    ArrayList的＆LT;整数GT; listOfPrimeNumbers =新的ArrayList＆LT;整数GT;（）;
    布尔[] isPrimeNumber =新的布尔[参数：initialCapacity + 1]; //布尔默认
    // 假
    而（指数＆LT; = listOfPrimeNumbers.size（））
    {
      isPrimeNumber [指数] =真;
      如果（isPrimeNumber [指数]）{
        listOfPrimeNumbers.add（指数）;
      }
      对于（INT J =指数;Ĵ*指数＆LT; =参数：initialCapacity; J ++）{
        isPrimeNumber [指数* J] = FALSE;
      }

      //现在标志着我多为非质数
      指数++;
    }
  }

}
 

解决方案

您可以设置listOfPrimeNumbers的初始容量，因为你可以估计有多少质数正在N.请参阅

http://en.wikipedia.org/wiki/Prime_number_theorem

但基本上N /（LN N）应该是listOfPrimeNumbers的初始容量。这将确保您的程序不会经常调整在幕后名单，这可能是昂贵的。

也就是说，如果你真的想成为有效的。如果你不关心，只需要设置该列表的东西更高的初始容量。现在，你必须将其设置为默认值，这意味着你的listOfPrimeNumbers将扩大。

编辑 - 我认为你有一个错误 - 行

  isPrimeNumber [指数] =真;
 

应该只有当指数是质数执行，因此将其移动到相应的if语句。同样，我不知道你的东西的作品，但我认为这是一个问题。

另一种方法是有一个地图为您isPrimeNumber检查。

I am trying to write a little script myself to compute all of the prime numbers up to n (a user submitted argument) and would appreciate a little bit of help. I want to use ArrayLists to write this function, and hopefully make it as efficient as possible - another big thing for me that I can't seem to grasp is doing everything as is standard and good practice (i.e having classes in capital letters, etc) so if you wouldn't mind please point out any mistakes in that regard so I can fix them.

Here is the code I have written thus far, but I know there are many ways of optimising it - specifically, I have a boolean array storing whether a number is prime or not. Surely there is a better way of doing this than cycling through the array and making everything prime, then getting rid of the numbers that are not ?

Thanks a lot for your time ! :)

(tl;dr - Writing a script to computer prime numbers up to N. I wish to use ArrayLists to do this. How can I make my code better - specifically the inefficient boolean array).

import java.util.*;
public class Prime {

  public static void main( String[] args ){

  }
  public static void prime( int initialCapacity){
    int index=0;
    ArrayList<Integer> listOfPrimeNumbers = new ArrayList<Integer>( );
    boolean[] isPrimeNumber = new boolean[initialCapacity + 1]; // boolean defaults to
    // false
    while ( index <= listOfPrimeNumbers.size() )
    {
      isPrimeNumber[index] = true;
      if (isPrimeNumber[index]) {
        listOfPrimeNumbers.add(index);
      }
      for (int j = index; j * index <= initialCapacity; j++) {
        isPrimeNumber[index * j] = false;
      }

      // Now mark the multiple of i as non-prime number
      index++;
    }
  }

}

解决方案

You can set the initial capacity of listOfPrimeNumbers, because you can estimate how many prime numbers are under N. See

http://en.wikipedia.org/wiki/Prime_number_theorem

but basically n / (ln n) should be the initial capacity of the listOfPrimeNumbers. This will ensure that your program does not constantly resize the list under the covers, which can be expensive.

That is, if you really want to be efficient. If you dont care, then just set the initial capacity of that list to something higher. Right now you have it set to the default, which means your listOfPrimeNumbers will have expand.

EDIT - I think you have an error -- the line

isPrimeNumber[index] = true;

should only be executed if index is a prime number, so move it into the appropriate if statement. Again, I don't know how your stuff works, but I think this is an issue.

An alternative would be to have a Map as your isPrimeNumber checker.

这篇关于计算素数最多N个整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！