流正整数的素因式分解
流正整数的素因式分解
提问于 2016-03-13 05:00:53
目前，我正试图将Java 8的Stream集成到我的日常Java工具箱中。我试图使用流来查找正整数的素因子，然后将每个因子存储在数组(或ArrayList)中，并将它们的多重性存储在并行数组中。或者，我试着创造一条.FactorWithMultiplicity对象，甚至是以因子为键、以多重性为值的Map。如果这些因素按升序排序，如果它甚至能够处理非常大的数字(比如，我敢说，Long.MAX_VALUE)，那就太好了。
目前，我的代码看起来是这样的，但是，由于我是流的初学者，我确信有一种更快或更合适的方式来完成这项任务。请使用流来创建您的解决方案，尽管如果您知道一些非流解决方案更快，请随时向我指出该代码。
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;回答 5
Stack Overflow用户
回答已采纳
发布于 2016-03-13 07:44:09
如果您特别想要一个基于流的解决方案，则可以有一个递归地对数字进行因素分析的方法：
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。
如果您想要考虑longs，这里有一个具有一些性能改进的版本：
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());Stack Overflow用户
发布于 2016-03-13 08:43:03
如果您想要重复调用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 ); }
}Stack Overflow用户
发布于 2016-03-13 15:34:31
要生成主要因素，您需要跟踪几个州。因此，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}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/35966710
复制相关文章
相似问题
腾讯云开发者
