Fermat Number in Java

2025 年 5 月 7 日 | 阅读 4 分钟

在本节中，我们将讨论什么是费马数，并创建 Java 程序来检查给定的数字是否为费马数。费马数程序经常出现在 Java 编程面试和学术中。

费马数

费马数首先由 Pierre de Fermat 研究。形式为2²^k +1（其中 k>=0）的非负奇数称为费马数。它表示为F_n。它是 OEIS 整数序列A000215**。

生成费马数很困难。因为它们用于密码学和伪随机数生成。它还有一些强大的数学特性。

费马数示例

前几个费马数是 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617。

前 10 个费马数

F₀ = 2²⁰ +1 = 3

F₁ = 2²¹ +1 = 5

F₂ = 2²² +1 = 17

F₃ = 2²³ +1 = 257

F₄ = 2²⁴ +1 = 65537

F⁵ = 2²⁵ +1=4294967297

F⁶ = 2²⁶ +1=18446744073709551617

F₇ = 2²⁷ +1 = 340282366920938463463374607431768211457

F₈ = 2²⁸ +1 = 115792089237316195423570985008687907853269984665640564039457584007913129639937

F₉ = 2²⁹ +1 =

134078079299425970995740249982058461274793658205923933777235614437217640300
73546976801874298166903427690031858186486050853753882811946569946433649006084097
有人推测，这个序列中只有前 5 个数字是素数。它是 OEIS 序列 A019434。

F₀ = 2²⁰ +1 = 3

F₁ = 2²¹ +1 = 5

F₂ = 2²² +1 = 17

F₃ = 2²³ +1 = 257

F₄ = 2²⁴ +1 = 65537

查找费马数的步骤

读取或初始化一个整数 n。
使用 Math.pow() 方法计算 2ⁿ 并将结果存储在一个变量 (p) 中。
现在，计算 2^p 并将结果存储在一个变量 (res) 中。
将变量 (res) 加 1，并将结果存储在一个变量 (f) 中。它是一个费马数。

让我们在 Java 程序中实现上述步骤。

费马数 Java 程序

FermatNumberExample1.java

import java.util.Scanner;
public class FermatNumberExample1
{
public static void main(String args[])
{ 
int n = 0;        
double result;
//executes until the condition becomes false
while (n <= 10) 
{
//logic to find Fermat number 
result = Math.pow (2, Math.pow(2, n)) + 1;
n++;
//prints the result
System.out.println (result);
} //end of while
}  
}

输出

3.0
5.0
17.0
257.0
65537.0
4.294967297E9
1.8446744073709552E19
3.4028236692093846E38
1.157920892373162E77
1.3407807929942597E154
Infinity

FermatNumberExample.java

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
public class FermatNumbers 
{
public static void main(String[] args) 
{
System.out.println("First 10 Fermat numbers:");
for ( int i = 0 ; i < 10 ; i++ ) 
{
System.out.printf("F[%d] = %s\n", i, fermat(i));
}
System.out.printf("%nFirst 12 Fermat numbers factored:%n");
for ( int i = 0 ; i < 13 ; i++ ) 
{
System.out.printf("F[%d] = %s\n", i, getString(getFactors(i, fermat(i))));
}
}
private static String getString(List<BigInteger> factors) 
{
if ( factors.size() == 1 ) 
{
return factors.get(0) + " (PRIME)";
}
return factors.stream().map(v -> v.toString()).map(v -> v.startsWith("-") ? "(C" + v.replace("-", "") + ")" : v).collect(Collectors.joining(" * "));
}
private static Map<Integer, String> COMPOSITE = new HashMap<>();
static 
{
COMPOSITE.put(9, "5529");
COMPOSITE.put(10, "6078");
COMPOSITE.put(11, "1037");
COMPOSITE.put(12, "5488");
COMPOSITE.put(13, "2884");
}
private static List<BigInteger> getFactors(int fermatIndex, BigInteger n) 
{
List<BigInteger> factors = new ArrayList<>();
BigInteger factor = BigInteger.ONE;
while (true) 
{
if (n.isProbablePrime(100)) 
{
factors.add(n);
break;
}
else 
{
if ( COMPOSITE.containsKey(fermatIndex) ) 
{
String stop = COMPOSITE.get(fermatIndex);
if ( n.toString().startsWith(stop) ) 
{
factors.add(new BigInteger("-" + n.toString().length()));
break;
}
}
factor = pollardRhoFast(n);
if (factor.compareTo(BigInteger.ZERO) == 0 ) 
{
factors.add(n);
break;
}
else 
{
factors.add(factor);
n = n.divide(factor);
}
}
}
return factors;
}
private static final BigInteger TWO = BigInteger.valueOf(2);
private static BigInteger fermat(int n) 
{
return TWO.pow((int)Math.pow(2, n)).add(BigInteger.ONE);
}
//  See:  https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
@SuppressWarnings("unused")
private static BigInteger pollardRho(BigInteger n) 
{
BigInteger x = BigInteger.valueOf(2);
BigInteger y = BigInteger.valueOf(2);
BigInteger d = BigInteger.ONE;
while ( d.compareTo(BigInteger.ONE) == 0 ) 
{
x = pollardRhoG(x, n);
y = pollardRhoG(pollardRhoG(y, n), n);
d = x.subtract(y).abs().gcd(n);
}
if (d.compareTo(n) == 0) 
{
return BigInteger.ZERO;
}
return d;
}
//Includes Speed Up of 100 multiples and 1 GCD, instead of 100 multiples and 100 GCDs.
//See Variants section of Wikipedia article.
//Testing F[8] = 1238926361552897 * Prime 
//This variant = 32 sec.
//Standard algorithm = 107 sec.
private static BigInteger pollardRhoFast(BigInteger n) 
{
long start = System.currentTimeMillis();
BigInteger x = BigInteger.valueOf(2);
BigInteger y = BigInteger.valueOf(2);
BigInteger d = BigInteger.ONE;
int count = 0;
BigInteger z = BigInteger.ONE;
while ( true ) 
{
x = pollardRhoG(x, n);
y = pollardRhoG(pollardRhoG(y, n), n);
d = x.subtract(y).abs();
z = z.multiply(d).mod(n);
count++;
if ( count == 100 ) 
{
d = z.gcd(n);
if ( d.compareTo(BigInteger.ONE) != 0 ) 
{
break;
}
z = BigInteger.ONE;
count = 0;
}
}
long end = System.currentTimeMillis();
System.out.printf("    Pollard rho try factor %s elapsed time = %d ms (factor = %s).%n", n, (end-start), d);
if ( d.compareTo(n) == 0 ) 
{
return BigInteger.ZERO;
}
return d;
}
private static BigInteger pollardRhoG(BigInteger x, BigInteger n) 
{
return x.multiply(x).add(BigInteger.ONE).mod(n);
}
}

输出

First 10 Fermat numbers:
F[0] = 3
F[1] = 5
F[2] = 17
F[3] = 257
F[4] = 65537
F[5] = 4294967297
F[6] = 18446744073709551617
F[7] = 340282366920938463463374607431768211457
F[8] = 115792089237316195423570985008687907853269984665640564039457584007913129639937
F[9] = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097

First 12 Fermat numbers factored:
F[0] = 3 (PRIME)
F[1] = 5 (PRIME)
F[2] = 17 (PRIME)
F[3] = 257 (PRIME)
F[4] = 65537 (PRIME)
    Pollard rho try factor 4294967297 elapsed time = 8 ms (factor = 641).
F[5] = 641 * 6700417
    Pollard rho try factor 18446744073709551617 elapsed time = 33 ms (factor = 274177).
F[6] = 274177 * 67280421310721

下一个主题使用 Java 查找幂集

Fermat Number in Java

费马数

费马数示例

查找费马数的步骤

费马数 Java 程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Fermat Number in Java

费马数

费马数示例

查找费马数的步骤

费马数 Java 程序

相关帖子

int vs Integer Java

Java 中的 2048 游戏

Java 本地化

Java BMI 计算器

Dijkstra Algorithm Java

Java 中 GSON 的 fromJson() 和 toJson() 方法的区别

Prim's algorithm Java

Java 中流式运行整数的中位数

如何在 Java 中创建不可修改的列表

如何在 Java 中为数组提供默认日期

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器