Tag: 素数

计算最多N个整数的素数

我正在尝试自己编写一个小脚本来计算所有素数到n（用户提交的参数），并希望得到一些帮助。 我想使用ArrayLists来编写这个函数，并希望尽可能高效 – 对于我来说，我似乎无法掌握的另一件大事就是做所有标准和良好实践（即用大写字母等等） ）所以，如果你不介意，请指出这方面的任何错误，以便我可以解决它们。 这是我到目前为止编写的代码，但我知道有很多方法可以优化它 – 具体来说，我有一个布尔数组存储数字是否为素数。 当然有一个更好的方法来做这个，而不是循环通过数组并使一切都是素数，然后摆脱不是的数字？ 非常感谢你的时间！ 🙂 （tl; dr – 将脚本编写到计算机素数最多为N.我希望使用ArrayLists来执行此操作。如何使我的代码更好 – 特别是低效的布尔数组）。 import java.util.*; public class Prime { public static void main( String[] args ){ } public static void prime( int initialCapacity){ int index=0; ArrayList listOfPrimeNumbers = new ArrayList( ); boolean[] isPrimeNumber = new boolean[initialCapacity + 1]; // boolean defaults […]

Prime测试，2位数字

我想打印所有2位数的素数。 这是我的代码： for(int input = 11; input <= 99; input += 2){ for(int x = 2; x < (int)Math.sqrt(input) + 1; x++){ if(input%x != 0){ System.out.println(input); break; }else{ break; } } } 问题是它打印的数字如35或49不是素数。

改进主筛算法

我正在尝试制作一个不错的Java程序，从1到N生成素数（主要用于Project Euler问题）。 目前，我的算法如下： 初始化一个布尔数组（如果N足够大则初始化为bitarray），因此它们都是假的，并且存储了一组用于存储素数的int。 设置一个整数，s等于最低素数，（即2） s是<= sqrt（N） 在数组/ bitarray中将s的所有倍数（从s ^ 2开始）设置为true。 找到array / bitarray中的下一个最小索引，该索引为false，将其用作s的新值。 ENDWHILE。 遍历数组/ bitarray，对于每个false的值，将相应的索引放在primes数组中。 现在，我试过跳过不是6k + 1或6k + 5forms的数字，但这只能让我加速~2倍，而我看到程序运行的速度比我的速度快（虽然非常复杂）代码），例如这里的那个 我该怎么做才能改善？ 编辑：好的，这是我的实际代码（对于1E7的N）： int l = 10000000, n = 2, sqrt = (int) Math.sqrt(l); boolean[] nums = new boolean[l + 1]; int[] primes = new int[664579]; while(n <= sqrt){ for(int i = 2 * […]

Prime生成数字查找器不能产生正确的输出

我正在解决这个问题： 考虑30：1,2,3,5,6,10,15,30的除数。 可以看出，对于每个除数d为30，d + 30 / d是素数。 找出所有正整数n的总和不超过100 000 000，这样对于n的每个除数d，d + n / d是素数。 我确信我有它，但是唉，它显然给了我错误的答案（ 12094504411074 ）。 我很确定我对Eratosthenes的筛子正在工作（但可能没有），所以我认为问题出在我的算法中。 它似乎得到正确的答案n = 30 （ 1+2+6+10+22+30 = 71 – 这是正确的吗？），但随着数字变大，它显然停止工作。 这是我的Java代码： import java.util.HashSet; public class Generators { static HashSet hSet = new HashSet(); public static void main(String[] args) { // TODO Auto-generated method stub int n = 100000000; […]

如何使用6 * k + – 1规则生成Primes

我们知道可以使用以下方法生成3以上的所有素数： 6 * k + 1 6 * k – 1 然而，我们从上面的公式生成的所有数字都不是素数。 For Example: 6 * 6 – 1 = 35 which is clearly divisible by 5. 为了消除这些条件，我使用Sieve方法并删除了数字，这些数字是从上面公式生成的数字的因子。 使用事实： 如果一个数字没有素数因素，那么它就是素数。 因为我们可以使用上面的公式生成所有素数。 如果我们可以删除上述数字的所有倍数，我们只剩下素数。 生成低于1000的素数。 ArrayList primes = new ArrayList(); primes.add(2);//explicitly add primes.add(3);//2 and 3 int n = 1000; for (int i = 1; i <= (n […]

面试问题：递归生成素数的最快方法是什么？

质数的生成很简单但是找到它并以递归方式生成（素数）的最快方法是什么？ 这是我的解决方案。 但是，这不是最好的方法。 我认为它是O（N * sqrt（N））。 如果我错了，请纠正我。 public static boolean isPrime(int n) { if (n < 2) { return false; } else if (n % 2 == 0 & n != 2) { return false; } else { return isPrime(n, (int) Math.sqrt(n)); } } private static boolean isPrime(int n, int i) { if (i < […]

从数组中打印出素数

我想用方法打印出数组中的所有素数。 我可以使用一个int，但不知道如何从数组返回某些数字。 感谢帮助！ public static boolean isPrime(int [] tab) { boolean prime = true; for (int i = 3; i <= Math.sqrt(tab[i]); i += 2) if (tab[i] % i == 0) { prime = false; break; } for(int i=0; i 2) || tab[i] == 2) { return true; } else { return false; } //return […]

如何打印素数到用户输入的整数？

大家下午好， 我目前正在尝试创建一个执行以下操作的程序： 开发一个代码，打印所有素数，直到用户输入的数字。 输出的一个例子： Enter an integer (2 or above): 19 The prime numbers up to you integer are: 2 3 5 7 11 13 17 19 不幸的是，还有一个需要满足的“要求”清单： 如果用户输入的数字低于2，则程序应打印一条消息，表明该数字无效，然后停止。 如果数字不能被除1和它本身之外的任何数字整除，则数字是素数。 对于这个程序，为了测试一个数字以查看它是否为素数，你应该尝试将数字除以从2到数字1的每个值，以查看它是否均匀分配。 例如： – 看5是否为素数：5不均匀分为2 5不均匀分为3 5不均匀分为4因此5是素数 – 看9是素数：9不均匀分为2 9除以3均为9因此9不是素数 该程序要求您编写嵌套循环（即循环内的循环）。 将使用一个循环从2到用户的数字进行计数，以便您可以测试这些数字中的每一个以确定它是否为素数。 对于这些数字中的每一个，x： 嵌套循环将检查从2到x-1的所有值，以查看x是否均匀划分。 您将需要使用布尔变量（也称为标志变量）来帮助您确定是否在屏幕上打印数字 上面的问题是关于我的代码到目前为止： import java.util。*; public class Something3 { public static void main(String[] […]

java的Prime编号程序

我是编程新手，需要java程序的帮助。 我希望我的程序返回1到10之间的所有素数。 for(int i=1; i<=10; i++){ int factors = 0; int j=1; while(j<=i){ if(i % j == 0){ factors++; } j++; } if(factors==2){ System.out.println(j); } } 我没有收到2,3,5和7，而是收到3,4,6和8

Java中的素数 – 算法

我已经开始学习使用Java编写代码并决定使用Project Euler站点给我一些小任务来尝试完成我学习的每一段新编码。 所以我遇到了问题3 ： 13195的主要因素是5,7,13和29. 600851475143的最大主要因素是什么？ 我想到了这个问题，并研究了很多关于素数的不同理论以及如何通过各种不同的计算找到它们（Sieve of Eratosthenes就是一个例子），我想到的解决方案是测试2 – > n中的数字并查看是否它们是素数，如果它们是那么我将把新发现的素数除以Tn变量（在这种情况下为600851475143）并查看它是否是一个因素。 如果是，我会将它分配给变量Hp（最高素数），在程序结束时我会将Hp输出到控制台以给出我的结果。 这是我的代码： public class Largest_Prime_Factor_NEW_SOLUTION { static long Tn = 600851475143L; static long Hp = 0; static boolean isPrime = false; public static void main(String[] args) { for (long i=2; i<Tn; i++) { System.out.println("TESTING NUMBER " + i); for (long k=2; k < […]