我需要一个方法来返回数组中的素数。
所以如果给出:primeArray(5)
比这样的数组应该返回:(2,3,5)
出于某种原因,这对我来说似乎不起作用:
public static int[] primeArray(int numFind)
{
//determines the size of the array returned
int primeTotal = 0;
//loop to find total prime numbers
for (int j = 1; j <= numFind; j ++)
{
if (isPrime(j))
primeTotal +=1;
}
//declare array to be returned
int[] numA = new int[primeTotal];
//current index of prime number
int iP = 0;
//loop to add prime elements to array
for (int x = 1; x <= numFind; x ++)
{
if (isPrime(x))
{
numA[iP]=x;
iP++; // <--- THIS IS CAUSING ME PROBLEMS
}
}
return numA;
}
public static boolean isPrime(int n)
{
for (int i = 2; i < n; i++)
{
if(n%i==0)
return false;
}
return true;
}
这就是我用来测试我的代码:
int[] num = primeArray(11);
System.out.println(num[0]);
System.out.println(num[1]);
但是对于输出我得到了这个:
1
2
但是,如果我评论出iP ++;比if语句最终决定只在素数作为参数传递时才执行:isPrime(j)但是如果违反了primeArray方法的全部目的,因为我需要primeArray方法来返回素数数组。
你的isPrime()
方法有问题。你需要为false
返回number < 2
。此外,你不需要迭代到n,只需迭代到n / 2甚至更好的sqrt(n)
。
将其更改为:
public static boolean isPrime(int n) {
if (n < 2) return false;
int maxIteration = Math.ceil(Math.sqrt(n));
for (int i = 2; i < maxIteration; i++) {
if(n % i == 0)
return false;
}
return true;
}
现在,考虑到你的真正问题(注意你的方法很好。如果改变了你的isPrime()
方法,它会返回正确的结果),但是你可以避免使用ArrayList
而不是数组迭代两次:
List<Integer> primes = new ArrayList<Integer>();
//loop to find total prime numbers
for (int j = 1; j <= numFind; j ++)
{
if (isPrime(j))
primes.add(j);
}
然后你可以返回素数,并将方法的返回类型更改为List<Integer>
而不是int[]
。
public static List<Integer> primeNumberList(int numFind)
如果你真的想要返回一个int[]
,那么你需要做一些工作将ArrayList
转换为int
数组。我把这个任务留给你了。只在SO上搜索这个,你会得到太多的帖子。
另外,如果要生成所有素数直到非常大的数,那么你应该看看Sieve of Eratosthenes
你只需要输出第一个到Array-Values的输出......
只需替换你的输出
for(int i = 0; i < num.length; i++)
{
System.out.println(num[i]);
}
你的代码运行正常。
在你的isPrime()
方法中,最后添加这一个语句
if(n < 2) return false;
我认为按照目前的方式,当1通过时,你会得到一个真实的。
我能想到的另一个建议是,如果你希望你的限制很小,你可以使用一个静态表来获取一定数量的数字。
static int[] PRIME_TABLE = {2,3,5,7,11,13,17,19,23,29,31};
等
因此,当此示例中的限制小于32时,您不需要计算其下面的所有素数,只需遍历此表并返回数字。
我尝试以不同的方式编写isPrime(int num)函数。代码变得有点冗长但有效。我使用不同的逻辑来识别数字是否为1,因为1既不是素数也不是复合数。代码如下。
static int count=0;
static boolean flag;
public static boolean isPrime(int num){
for(int i = 1; i<=num/2 ; i++){
if(num%i ==0){
count++;
if(count >=2){
flag = false;
}
else{
if( num/1==1){
flag = false;
}
else{
flag = true;
}
}
}
}
return flag;
}
此代码返回小于n的所有素数
public ArrayList<Integer> allPrimesLessThanN( int n) {
int sqrtN = (int)Math.sqrt(n);
int [] numberList = new int[n];
ArrayList<Integer> primeList = new ArrayList<>();
for( int i = 0; i < n ; i++)
{
numberList[i] = i+1;
}
int k = 2;
while( k <= sqrtN)
{
if(numberList[k+1] != 0)
{
for( int j = k+1; j < n; j++)
{
if( numberList[j] % k == 0)
{
numberList[j] = 0;
}
}
}
k++;
}
for( int i = 1; i < n; i++)
{
if(numberList[i] != 0)
primeList.add(numberList[i]);
}
return primeList;
}
有几种方法可以获得素数数组,最简单的计算方法是使用Eratosthenes筛选。这将迭代每个递增的数字,其中当找到下一个素数时,其后续的所有倍数都标记为非素数。大多数实现使用如下的布尔数组:
boolean[] numbers = new boolean[max];
// At first, assume every number is prime
for (int i = 0; i < max; i++)
numbers[i] = true;
// Zero and one are not primes
numbers[0] = number[1] = false;
// Begin iteration from 2, the smallest prime
for (int i = 2; i < max; i++) {
// if i is prime, all multiples of i are not prime
if (numbers[i]) {
for (int j = i * 2; j < max; j += i) {
numbers[j] = false;
}
}
}
此方法适用于快速生成素数数组的方法,但对于较大的最大限制,它可能会占用大量内存。
解决这个问题的另一种方法是你已经完成它的方式,你只需在找到它时添加下一个素数。您可以通过以下方式提高实施效率。
boolean isPrime(double p) {
if (p < 2) return false;
for (int i = 2; i <= Math.sqrt(p); i++) if (p % i == 0) return false;
return true;
}
从Rohit Jain建议的纠正实施开始(如上所述),您可能会注意到您不必测试每个小于sqrt(p)
的数字。如果p
不能被n
整除,那么它就不会被n
的倍数整除 - 这样我们只需要测试p
以下的每个素数。例如;因为7不能被2整除,所以它也不会被4整除。
这里的问题是我们现在需要找到小于sqrt(p)
的数字来测试p。啊,但不,我们不!我们可以查看我们稍后将在其他方法中返回的已知素数的缓存列表。虽然我们正在缓存一个已知素数列表,但我们也不需要在另一个方法中创建一个新列表,我们可以只返回我们的缓存(一旦生成)!成品看起来像这样:
class Primes {
private static final List<Double> known_primes = new ArrayList<Double>(Collections.singletonList(2d));
public static boolean isPrime(double p) {
if (p < 2) return false; // 2 already in our cache
if (known_primes.contains(p)) return true; // found prime in cache
for (double i = 3; i <= Math.sqrt(p); i += 2) { // only check odd numbers
if (!isPrime(i)) continue; // only check primes
if (p % i == 0) return false; // p is divisible by i, so not prime
}
// checked all possible divisors, so p must be prime - cache and sort it!
known_primes.add(p);
Collections.sort(known_primes);
return true;
}
}
现在你可以使用Primes.isPrime(...)
来检查;)