使用流对正整数进行质因数分解
Prime Factorization of a Positive Integer with Streams
我目前正在尝试将 Java 8 的 Stream API 合并到我的日常 Java 工具箱中。我正在尝试使用 Streams 来查找正整数的质因数,然后将每个因数存储在一个数组(或 ArrayList
)中,并将它们的多重性存储在一个并行数组中。或者,我正在尝试创建一个 say... FactorWithMultiplicity
对象的流,甚至是一个 Map
以因子为键、多重性为值的对象。如果因子按升序排序,并且它甚至可以处理非常大的数字(例如,我敢说,Long.MAX_VALUE
),那就太好了。
目前,我的代码看起来像这样,但是,由于我是 Streams 的初学者,我确信有更快或更适合的方法来完成此任务。请使用 Streams 创建您的解决方案,如果您知道某些非 Stream 解决方案更快,请随时向我指出该代码。
int num = getPositiveInt();
ArrayList<Integer> factors = new ArrayList<>();
ArrayList<Integer> multiplicities = new ArrayList<>();
boolean isPrime = IntStream.rangeClosed(2, num / 2)
.reduce(num, (int temp, int factor) -> {
int count = 0;
while (temp % factor == 0) {
temp /= factor;
count++;
}
if (count > 0) {
factors.add(factor);
multiplicities.add(count);
}
return temp;
}) > 1;
分解整数时,最有利可图的优化是尝试除数直到数字的平方根(包括在内,例如:尝试分解 49)。另外,检查2之后,你可以只检查奇数。
int num = getPositiveInt();
ArrayList<Integer> factors = new ArrayList<>();
ArrayList<Integer> multiplicities = new ArrayList<>();
int factor = 2;
int f_delta = 1; // to increase by +1 only once (2 to 3)
while ((factor*factor)<=num) {
int count = 0;
while (num % factor == 0) {
num /= factor;
count++;
}
if (count > 0) {
factors.add(factor);
multiplicities.add(count);
}
factor += f_delta;
f_delta = 2;
}
经过彻底调查,我发现与我在问题中发布的内容相比,这在速度上有了压倒性的提高。唯一更快的是 @Misha 在将他们的 factors
函数更改为使用 .rangeClosed(prevFactor, Math.sqrt(num))
之后发布的那个。但是,this other solution 是最快的解决方案……期间……但不使用流。
public static Map<Long, Integer> factorize(long num) { //NOW USING LONG
Map<Long, Integer> factors = new LinkedHashMap<>(); //NOW USING MAP
long lastRemainder = LongStream.rangeClosed(2, (long) Math.sqrt(num)) //NOW USING SQRT
.filter(x -> (x== 2||x%2>0)&&(x==3||x%3>0)&&(x==5||x%5>0)) //ADDED THIS
.reduce(num, (temp, factor) -> {
if (factor <= temp / factor) { //ADDED THIS
int count = 0;
while (temp % factor == 0) {
temp /= factor;
count++;
}
if (count > 0)
factors.put(factor, count);
}
return temp;
});
if (lastRemainder != num && lastRemainder > 1) //ADDED THIS
factors.put(lastRemainder, 1);
return factors;
}
如果您特别想要一个基于流的解决方案,您可以使用递归因式分解数字的方法:
IntStream factors(int num) {
return IntStream.range(2, num)
.filter(x -> num % x == 0)
.mapToObj(x -> IntStream.concat(IntStream.of(x), factors(num / x)))
.findFirst()
.orElse(IntStream.of(num));
}
然后你可以使用下面的代码来制作你的两个列表:
Map<Integer, Integer> f2m = factors(2, num).boxed()
.collect(toMap(f -> f, f -> 1, Integer::sum)); // or groupingBy with summingInt(f->1), whichever you prefer
List<Integer> factors = new ArrayList<>(f2m.keySet());
List<Integer> multiplicities = factors.stream().map(f2m::get).collect(toList());
如果你想从中获得更多的性能,你可以将最后找到的因子传递给 factors
方法并使用它而不是 2
。
如果您想对多头进行因子分解,这里有一个具有一些性能改进的版本:
static LongStream factors(long lastFactor, long num) {
return LongStream.rangeClosed(lastFactor, (long) Math.sqrt(num))
.filter(x -> num % x == 0)
.mapToObj(x -> LongStream.concat(LongStream.of(x), factors(x, num / x)))
.findFirst()
.orElse(LongStream.of(num));
}
如果你希望结果是有序的,你可以使用
SortedMap<Long, Integer> f2m = factors(2, num).boxed()
.collect(toMap(f -> f, f -> 1, Integer::sum, TreeMap::new));
或者,保持 Map
不变并使用
List<Long> factors = f2m.keySet().stream().sorted().collect(toList());
另一种变体,如果您想重复调用 factorsOf
,它会很有用。 (我从某处偷走了筛子的基本思想,修复了它。)
这里的想法是使用质数作为流,过滤因子并确定它们的多重性以创建 FactorTimes 对象来确定结果。
public class PrimeFactors {
private final int limit = 1_000_000;
private BitSet sieve = new BitSet( limit+1 );
public PrimeFactors(){
sieve.set( 2, limit );
long count = sieve.stream()
.peek( x -> { if( (long)x*x < limit )
for( int i = x*x; i <= limit; i += x )
sieve.clear( i );
})
.count();
}
public FactorTimes[] factorsOf( int num ){
FactorTimes[] fts = sieve.stream()
.limit( num/2 )
.filter( x -> num % x == 0 )
.mapToObj( x -> { int n = 1;
int k = num/x;
while( k % x == 0 ){ k /= x; n++; }
return new FactorTimes( x, n );
} )
.toArray( FactorTimes[]::new );
return fts;
}
public static void main( String[] args ){
PrimeFactors pf = new PrimeFactors();
for( FactorTimes ft: pf.factorsOf( 4504500 ) ){
System.out.println( ft );
}
}
}
class FactorTimes {
private int factor, multiplicity;
public FactorTimes(int f, int m) {
factor = f; multiplicity = m;
}
public int getFactor() { return factor; }
public int getMultiplicity() { return multiplicity; }
public String toString(){
return multiplicity > 1 ? factor + "(" + multiplicity + ")"
: Integer.toString( factor ); }
}
要生成主要因素,您需要跟踪多个状态。因此Streams
不太适合这个任务。
你可以做的是提供一个自己的 Spliterator
来创建一个 IntStream
。现在您可以生成数组或分组操作了:
public static IntStream primeFactors(int n) {
int characteristics = Spliterator.ORDERED | Spliterator.SORTED | Spliterator.IMMUTABLE | Spliterator.NONNULL;
Spliterator.OfInt spliterator = new Spliterators.AbstractIntSpliterator(Long.MAX_VALUE, characteristics) {
int val = n;
int div = 2;
@Override
public boolean tryAdvance(IntConsumer action) {
while (div <= val) {
if (val % div == 0) {
action.accept(div);
val /= div;
return true;
}
div += div == 2 ? 1 : 2;
}
return false;
}
@Override
public Comparator<? super Integer> getComparator() {
return null;
}
};
return StreamSupport.intStream(spliterator, false);
}
然后这样调用:
int n = 40500;
System.out.println(Arrays.toString(primeFactors(n).toArray()));
System.out.println(primeFactors(n).boxed().collect(
Collectors.groupingBy(Function.identity(), Collectors.summingInt(i -> 1)))
);
您应该会得到想要的结果:
[2, 2, 3, 3, 3, 3, 5, 5, 5]
{2=2, 3=4, 5=3}
我目前正在尝试将 Java 8 的 Stream API 合并到我的日常 Java 工具箱中。我正在尝试使用 Streams 来查找正整数的质因数,然后将每个因数存储在一个数组(或 ArrayList
)中,并将它们的多重性存储在一个并行数组中。或者,我正在尝试创建一个 say... FactorWithMultiplicity
对象的流,甚至是一个 Map
以因子为键、多重性为值的对象。如果因子按升序排序,并且它甚至可以处理非常大的数字(例如,我敢说,Long.MAX_VALUE
),那就太好了。
目前,我的代码看起来像这样,但是,由于我是 Streams 的初学者,我确信有更快或更适合的方法来完成此任务。请使用 Streams 创建您的解决方案,如果您知道某些非 Stream 解决方案更快,请随时向我指出该代码。
int num = getPositiveInt();
ArrayList<Integer> factors = new ArrayList<>();
ArrayList<Integer> multiplicities = new ArrayList<>();
boolean isPrime = IntStream.rangeClosed(2, num / 2)
.reduce(num, (int temp, int factor) -> {
int count = 0;
while (temp % factor == 0) {
temp /= factor;
count++;
}
if (count > 0) {
factors.add(factor);
multiplicities.add(count);
}
return temp;
}) > 1;
分解整数时,最有利可图的优化是尝试除数直到数字的平方根(包括在内,例如:尝试分解 49)。另外,检查2之后,你可以只检查奇数。
int num = getPositiveInt();
ArrayList<Integer> factors = new ArrayList<>();
ArrayList<Integer> multiplicities = new ArrayList<>();
int factor = 2;
int f_delta = 1; // to increase by +1 only once (2 to 3)
while ((factor*factor)<=num) {
int count = 0;
while (num % factor == 0) {
num /= factor;
count++;
}
if (count > 0) {
factors.add(factor);
multiplicities.add(count);
}
factor += f_delta;
f_delta = 2;
}
经过彻底调查,我发现与我在问题中发布的内容相比,这在速度上有了压倒性的提高。唯一更快的是 @Misha 在将他们的 factors
函数更改为使用 .rangeClosed(prevFactor, Math.sqrt(num))
之后发布的那个。但是,this other solution 是最快的解决方案……期间……但不使用流。
public static Map<Long, Integer> factorize(long num) { //NOW USING LONG
Map<Long, Integer> factors = new LinkedHashMap<>(); //NOW USING MAP
long lastRemainder = LongStream.rangeClosed(2, (long) Math.sqrt(num)) //NOW USING SQRT
.filter(x -> (x== 2||x%2>0)&&(x==3||x%3>0)&&(x==5||x%5>0)) //ADDED THIS
.reduce(num, (temp, factor) -> {
if (factor <= temp / factor) { //ADDED THIS
int count = 0;
while (temp % factor == 0) {
temp /= factor;
count++;
}
if (count > 0)
factors.put(factor, count);
}
return temp;
});
if (lastRemainder != num && lastRemainder > 1) //ADDED THIS
factors.put(lastRemainder, 1);
return factors;
}
如果您特别想要一个基于流的解决方案,您可以使用递归因式分解数字的方法:
IntStream factors(int num) {
return IntStream.range(2, num)
.filter(x -> num % x == 0)
.mapToObj(x -> IntStream.concat(IntStream.of(x), factors(num / x)))
.findFirst()
.orElse(IntStream.of(num));
}
然后你可以使用下面的代码来制作你的两个列表:
Map<Integer, Integer> f2m = factors(2, num).boxed()
.collect(toMap(f -> f, f -> 1, Integer::sum)); // or groupingBy with summingInt(f->1), whichever you prefer
List<Integer> factors = new ArrayList<>(f2m.keySet());
List<Integer> multiplicities = factors.stream().map(f2m::get).collect(toList());
如果你想从中获得更多的性能,你可以将最后找到的因子传递给 factors
方法并使用它而不是 2
。
如果您想对多头进行因子分解,这里有一个具有一些性能改进的版本:
static LongStream factors(long lastFactor, long num) {
return LongStream.rangeClosed(lastFactor, (long) Math.sqrt(num))
.filter(x -> num % x == 0)
.mapToObj(x -> LongStream.concat(LongStream.of(x), factors(x, num / x)))
.findFirst()
.orElse(LongStream.of(num));
}
如果你希望结果是有序的,你可以使用
SortedMap<Long, Integer> f2m = factors(2, num).boxed()
.collect(toMap(f -> f, f -> 1, Integer::sum, TreeMap::new));
或者,保持 Map
不变并使用
List<Long> factors = f2m.keySet().stream().sorted().collect(toList());
另一种变体,如果您想重复调用 factorsOf
,它会很有用。 (我从某处偷走了筛子的基本思想,修复了它。)
这里的想法是使用质数作为流,过滤因子并确定它们的多重性以创建 FactorTimes 对象来确定结果。
public class PrimeFactors {
private final int limit = 1_000_000;
private BitSet sieve = new BitSet( limit+1 );
public PrimeFactors(){
sieve.set( 2, limit );
long count = sieve.stream()
.peek( x -> { if( (long)x*x < limit )
for( int i = x*x; i <= limit; i += x )
sieve.clear( i );
})
.count();
}
public FactorTimes[] factorsOf( int num ){
FactorTimes[] fts = sieve.stream()
.limit( num/2 )
.filter( x -> num % x == 0 )
.mapToObj( x -> { int n = 1;
int k = num/x;
while( k % x == 0 ){ k /= x; n++; }
return new FactorTimes( x, n );
} )
.toArray( FactorTimes[]::new );
return fts;
}
public static void main( String[] args ){
PrimeFactors pf = new PrimeFactors();
for( FactorTimes ft: pf.factorsOf( 4504500 ) ){
System.out.println( ft );
}
}
}
class FactorTimes {
private int factor, multiplicity;
public FactorTimes(int f, int m) {
factor = f; multiplicity = m;
}
public int getFactor() { return factor; }
public int getMultiplicity() { return multiplicity; }
public String toString(){
return multiplicity > 1 ? factor + "(" + multiplicity + ")"
: Integer.toString( factor ); }
}
要生成主要因素,您需要跟踪多个状态。因此Streams
不太适合这个任务。
你可以做的是提供一个自己的 Spliterator
来创建一个 IntStream
。现在您可以生成数组或分组操作了:
public static IntStream primeFactors(int n) {
int characteristics = Spliterator.ORDERED | Spliterator.SORTED | Spliterator.IMMUTABLE | Spliterator.NONNULL;
Spliterator.OfInt spliterator = new Spliterators.AbstractIntSpliterator(Long.MAX_VALUE, characteristics) {
int val = n;
int div = 2;
@Override
public boolean tryAdvance(IntConsumer action) {
while (div <= val) {
if (val % div == 0) {
action.accept(div);
val /= div;
return true;
}
div += div == 2 ? 1 : 2;
}
return false;
}
@Override
public Comparator<? super Integer> getComparator() {
return null;
}
};
return StreamSupport.intStream(spliterator, false);
}
然后这样调用:
int n = 40500;
System.out.println(Arrays.toString(primeFactors(n).toArray()));
System.out.println(primeFactors(n).boxed().collect(
Collectors.groupingBy(Function.identity(), Collectors.summingInt(i -> 1)))
);
您应该会得到想要的结果:
[2, 2, 3, 3, 3, 3, 5, 5, 5]
{2=2, 3=4, 5=3}