Java中的Prime分解程序
我正在研究用Java实现的素数分解程序。 目标是找到最大的素数因子600851475143（ 项目欧拉问题3 ）。 我想我已经完成了大部分工作，但是我遇到了一些错误。 此外，我的逻辑似乎已关闭，特别是我设置的用于检查数字是否为素数的方法。
public class PrimeFactor { public static void main(String[] args) { int count = 0; for (int i = 0; i < Math.sqrt(600851475143L); i++) { if (Prime(i) && i % Math.sqrt(600851475143L) == 0) { count = i; System.out.println(count); } } } public static boolean Prime(int n) { boolean isPrime = false; // A number is prime iff it is divisible by 1 and itself only if (n % n == 0 && n % 1 == 0) { isPrime = true; } return isPrime; } } 编辑
public class PrimeFactor { public static void main(String[] args) { for (int i = 2; i <= 600851475143L; i++) { if (isPrime(i) == true) { System.out.println(i); } } } public static boolean isPrime(int number) { if (number == 1) return false; if (number == 2) return true; if (number % 2 == 0) return false; for (int i = 3; i <= number; i++) { if (number % i == 0) return false; } return true; } }
为什么要这么复杂？ 你不需要像isPrime（）那样做任何事情。 除以它的最小除数（素数）并从这个素数做循环。 这是我的简单代码：
public class PrimeFactor { public static int largestPrimeFactor(long number) { int i; for (i = 2; i <= number; i++) { if (number % i == 0) { number /= i; i--; } } return i; } /** * @param args */ public static void main(String[] args) { System.out.println(largestPrimeFactor(13195)); System.out.println(largestPrimeFactor(600851475143L)); } }
编辑：我希望这听起来并不是一个令人难以置信的居高临下的答案。 我只是想说明一下，从计算机的角度来看，你必须检查所有可能是X因子的数字，以确保它是最佳的。 计算机只是通过查看就不知道它是复合的，所以你必须迭代
示例：X是素数吗？
对于X = 67的情况：
你怎么检查这个？
I divide it by 2... it has a remainder of 1 (this also tells us that 67 is an odd number) I divide it by 3... it has a remainder of 1 I divide it by 4... it has a remainder of 3 I divide it by 5... it has a remainder of 2 I divide it by 6... it has a remainder of 1
事实上，如果数字不是素数，你只会得到0的余数。
你是否必须检查每个小于X的数字以确保它是素数？ 不。 不再了，多亏了数学（！）
让我们看一个较小的数字，比如16。
16不是素数。
为什么？ 因为
2*8 = 16 4*4 = 16
因此，16可以均匀地除以1和它本身。 （虽然“1”在技术上不是素数，但这是技术性的，我离题了）
所以我们将16除以1 …当然这是有效的，这适用于每个数字
Divide 16 by 2... we get a remainder of 0 (8*2) Divide 16 by 3... we get a remainder of 1 Divide 16 by 4... we get a remainder of 0 (4*4) Divide 16 by 5... we get a remainder of 1 Divide 16 by 6... we get a remainder of 4 Divide 16 by 7... we get a remainder of 2 Divide 16 by 8... we get a remainder of 0 (8*2)
我们实际上只需要一个0的余数来告诉我们它的复合（与“素数”相反的是“复合”）。
检查16是否可被2整除与检查它是否可被8整除是一回事，因为2和8乘以得到16。
我们只需要检查一部分频谱（从2到X的平方根），因为我们可以乘以的最大数是sqrt（X），否则我们使用较小的数来得到多余的答案。
是17素数？
17 % 2 = 1 17 % 3 = 2 17 % 4 = 1 <--| approximately the square root of 17 [4.123...] 17 % 5 = 2 <--| 17 % 6 = 5 17 % 7 = 3
sqrt（X）之后的结果，如17 % 7等等，是多余的，因为它们必须乘以小于sqrt（X）的东西才能得到X.
那是，
A * B = X.
如果A和B都大于sqrt（X）那么
A * B将产生一个大于X的数字。
因此，A或B中的一个必须小于sqrt（X），并且检查这两个值是多余的，因为您只需要知道其中一个是否均匀地划分X（偶数除法为您提供另一个值一个答案）
我希望有所帮助。
编辑：有更复杂的检查素数的方法，Java有一个内置的“这个数字可能是素数”或BigInteger类中的“这个数字肯定是复合的”方法，因为我最近通过另一个SO答案：
您需要对用于分解大数的算法进行一些研究; 这个维基百科页面看起来是个好地方。 在第一段中，它指出：
当数字非常大时，没有公认的有效整数分解算法……
但它确实列出了许多特殊和通用算法。 你需要选择一个能够很好地处理12个十进制数字的数字。 这些数字对于最天真的工作方法而言太大了，但足够小（例如）基于枚举从2开始的素数的方法可行。 （提示 – 从Erasthones的筛子开始）
这是一个非常优雅的答案 – 它使用蛮力（不是一些花哨的算法），但是以一种聪明的方式 – 通过降低限制，因为我们找到素数并通过这些素数进行复合…
它还只打印素数 – 而且只打印素数，如果一个素数在产品中超过一次 – 它将打印它与产品中的素数一样多次。
public class Factorization { public static void main(String[] args) { long composite = 600851475143L; int limit = (int)Math.sqrt(composite)+1; for (int i=3; i
你想从2 – > n-1迭代并确保n％i！= 0.这是检查素性的最天真的方法。 如上所述，如果数量很大，这非常非常慢。
要找到因素，您需要以下内容：
long limit = sqrt(number); for (long i=3; i
我觉得你很困惑，因为没有iff [if-and-only-if]运算符。
转到有问题的整数的平方根是一个很好的捷径。 剩下的就是检查该循环中的数字是否均匀分配。 这只是[大数字]％i == 0.没有理由你的Primefunction。
因为你正在寻找最大的除数，另一个技巧是从小于平方根的最高整数开始然后去i–。
像其他人所说，最终，这是非常缓慢的。
private static boolean isPrime(int k) throws IllegalArgumentException { int j; if (k < 2) throw new IllegalArgumentException("All prime numbers are greater than 1."); else { for (j = 2; j < k; j++) { if (k % j == 0) return false; } } return true; } public static void primeFactorsOf(int n) { boolean found = false; if (isPrime(n) == true) System.out.print(n + " "); else { int i = 2; while (found == false) { if ((n % i == 0) && (isPrime(i))) { System.out.print(i + ", "); found = true; } else i++; } primeFactorsOf(n / i); } }
对于那些使用方法isPrime(int) : boolean答案，有一个比之前实现的算法更快的算法（类似的）
private static boolean isPrime(long n) { //when n >= 2 for (int k = 2; k < n; k++) if (n % k == 0) return false; return true; }
这是这样的：
private static boolean isPrime(long n) { //when n >= 2 if (n == 2 || n == 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int k = 1; k <= (Math.floor(Math.sqrt(n)) + 1) / 6; k++) if (n % (6 * k + 1) == 0 || n % (6 * k - 1) == 0) return false; return true; }
我使用两个事实制作了这个算法：
- 我们只需要检查
n % k == 0直到k <= Math.sqrt(n)。 这是事实，因为对于任何更高的因素，因素仅仅是“翻转”ex。 考虑n = 15的情况，其中3 * 5=5 * 3，并且5>Math.sqrt(15)。 当我们可以检查其中一个表达式时，不需要检查15 % 3 == 0和15 % 5 == 0重叠。 - 所有素数（不包括
2和3）都可以表示为(6 * k) + 1或(6 * k) - 1，因为任何正整数都可以表示为(6 * k) + n，其中n = -1, 0, 1, 2, 3, or 4并且k是整数<= 0，并且n = 0, 2, 3, and 40,2,3n = 0, 2, 3, and 4情况都是可还原的。
因此，如果n不能被2或整数forms6k ± 1 <= Math.sqrt(n)整除，则n为素数。 因此上述算法。
-
关于素性测试的维基百科文章
-
编辑：以为我可能会发布我的完整解决方案（*我没有使用isPrime() ，我的解决方案几乎与最佳答案相同，但我认为我应该回答实际问题）：
public class Euler3 { public static void main(String[] args) { long[] nums = {13195, 600851475143L}; for (num : nums) System.out.println("Largest prime factor of " + num + ": " + lpf(num)); } private static lpf(long n) { long largestPrimeFactor = 1; long maxPossibleFactor = n / 2; for (long i = 2; i <= maxPossibleFactor; i++) if (n % i == 0) { n /= i; largestPrimeFactor = i; i--; } return largestPrimeFactor; } }
找到所有素数因子分解
import java.math.BigInteger; import java.util.Scanner; public class BigIntegerTest { public static void main(String[] args) { BigInteger myBigInteger = new BigInteger("65328734260653234260");//653234254 BigInteger originalBigInteger; BigInteger oneAddedOriginalBigInteger; originalBigInteger=myBigInteger; oneAddedOriginalBigInteger=originalBigInteger.add(BigInteger.ONE); BigInteger index; BigInteger countBig; for (index=new BigInteger("2"); index.compareTo(myBigInteger.add(BigInteger.ONE)) <0; index = index.add(BigInteger.ONE)){ countBig=BigInteger.ZERO; while(myBigInteger.remainder(index) == BigInteger.ZERO ){ myBigInteger=myBigInteger.divide(index); countBig=countBig.add(BigInteger.ONE); } if(countBig.equals(BigInteger.ZERO)) continue; System.out.println(index+ "**" + countBig); } System.out.println("Program is ended!"); } }
我的编程课遇到了一个非常类似的问题。 在我的课堂上，它必须计算输入的数字。 我使用的解决方案与Stijak非常相似。 我编辑了我的代码来处理这个问题的数字，而不是使用输入。
与Stijak代码的一些区别是：
我在代码中考虑了偶数。
我的代码只打印最大的素数因子，而不是所有因素。
在我将当前因子的所有实例都分开之前，我不会重新计算factorLimit。
我声明了所有变量，因为我希望能够灵活地将它用于非常大的数字值。 我发现最坏的情况是一个非常大的素数，如9223372036854775783，或者是一个非常大的数，其素数平方根如9223371994482243049.数字越多，算法运行得越快。 因此，最好的情况是4611686018427387904（2 ^ 62）或6917529027641081856（3 * 2 ^ 61）这样的数字，因为它们都有62个因子。
public class LargestPrimeFactor { public static void main (String[] args){ long number=600851475143L, factoredNumber=number, factor, factorLimit, maxPrimeFactor; while(factoredNumber%2==0) factoredNumber/=2; factorLimit=(long)Math.sqrt(factoredNumber); for(factor=3;factor<=factorLimit;factor+=2){ if(factoredNumber%factor==0){ do factoredNumber/=factor; while(factoredNumber%factor==0); factorLimit=(long)Math.sqrt(factoredNumber); } } if(factoredNumber==1) if(factor==3) maxPrimeFactor=2; else maxPrimeFactor=factor-2; else maxPrimeFactor=factoredNumber; if(maxPrimeFactor==number) System.out.println("Number is prime."); else System.out.println("The largest prime factor is "+maxPrimeFactor); } }
public class Prime { int i; public Prime( ) { i = 2; } public boolean isPrime( int test ) { int k; if( test < 2 ) return false; else if( test == 2 ) return true; else if( ( test > 2 ) && ( test % 2 == 0 ) ) return false; else { for( k = 3; k < ( test/2 ); k += 2 ) { if( test % k == 0 ) return false; } } return true; } public void primeFactors( int factorize ) { if( isPrime( factorize ) ) { System.out.println( factorize ); i = 2; } else { if( isPrime( i ) && ( factorize % i == 0 ) ) { System.out.print( i+", " ); primeFactors( factorize / i ); } else { i++; primeFactors( factorize ); } } public static void main( String[ ] args ) { Prime p = new Prime( ); p.primeFactors( 649 ); p.primeFactors( 144 ); p.primeFactors( 1001 ); } }