假设有一组数字，我们希望找到最大的最小素因数。为了加快搜索速度，因式分解应该使用单独的线程或进程并行执行，以充分利用CPU的多个核。
C
使用gcc -Wall -std=c99 -fopenmp编译，其中需要gcc 4.2或更高版本。
#include <stdio.h>
#include <omp.h>
//Using OpenMP
int main()
{
int data[] = {
12757923, 12878611, 12878893, 12757923, 15808973, 15780709, 197622519};int largest, largest_factor = 0;omp_set_num_threads(4);/* "omp parallel for" turns the for loop multithreaded by making each thread* iterating only a part of the loop variable, in this case i; variables declared* as "shared" will be implicitly locked on access*/#pragma omp parallel for shared(largest_factor, largest)for (int i = 0; i < 7; i++) {
int p, n = data[i];for (p = 3; p * p <= n && n % p; p += 2);if (p * p > n) p = n;if (p > largest_factor) {
largest_factor = p;largest = n;printf("thread %d: found larger: %d of %d\n",omp_get_thread_num(), p, n);} else {
printf("thread %d: not larger: %d of %d\n",omp_get_thread_num(), p, n);}}printf("Largest factor: %d of %d\n", largest_factor, largest);return 0;
}
输出：
thread 1: found larger: 47 of 12878893
thread 0: not larger: 3 of 12757923
thread 0: not larger: 47 of 12878611
thread 3: not larger: 3 of 197622519
thread 2: not larger: 29 of 15808973
thread 2: not larger: 7 of 15780709
thread 1: not larger: 3 of 12757923
Largest factor: 47 of 12878893
C#
using System;
using System.Collections.Generic;
using System.Linq;class Program
{
public static List<int> PrimeFactors(int number){
var primes = new List<int>();for (int div = 2; div <= number; div++){
while (number % div == 0){
primes.Add(div);number = number / div;}}return primes;}static void Main(string[] args){
int[] n = {
12757923, 12878611, 12757923, 15808973, 15780709, 197622519 };// Calculate each of those numbers' prime factors, in parallelvar factors = n.AsParallel().Select(PrimeFactors).ToList();// Make a new list showing the smallest factor for eachvar smallestFactors = factors.Select(thisNumbersFactors => thisNumbersFactors.Min()).ToList();// Find the index that corresponds with the largest of those factorsint biggestFactor = smallestFactors.Max();int whatIndexIsThat = smallestFactors.IndexOf(biggestFactor);Console.WriteLine("{0} has the largest minimum prime factor: {1}", n[whatIndexIsThat], biggestFactor);Console.WriteLine(string.Join(" ", factors[whatIndexIsThat]));}
}
输出：
12878611 has the largest minimum prime factor: 47
47 101 2713
另一个使用Parallel.For的版本：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;private static void Main(string[] args)
{
int j = 0, m = 0;decimal[] n = {
12757923, 12878611, 12757923, 15808973, 15780709, 197622519};var l = new List<int>[n.Length];Parallel.For(0, n.Length, i => {
l[i] = getPrimes(n[i]); });for (int i = 0; i<n.Length; i++)if (l[i].Min()>m){
m = l[i].Min();j = i;}Console.WriteLine("Number {0} has largest minimal factor:", n[j]);foreach (int list in l[j])Console.Write(" "+list);
}
输出：
Number 12878611 has largest minimal factor:47 101 2713
C++
库：Microsoft Parallel Patterns Library (PPL)
//using C++11 features including lambda functions.
#include <iostream>
#include <iterator>
#include <vector>
#include <ppl.h> // MSVC++
#include <concurrent_vector.h> // MSVC++struct Factors
{
int number;std::vector<int> primes;
};const int data[] =
{
12757923, 12878611, 12878893, 12757923, 15808973, 15780709, 197622519
};int main()
{
// concurrency-safe container replaces std::vector<>Concurrency::concurrent_vector<Factors> results;// parallel algorithm replaces std::for_each()Concurrency::parallel_for_each(std::begin(data), std::end(data), [&](int n){
Factors factors;factors.number = n;for (int f = 2; n > 1; ++f){
while (n % f == 0){
factors.primes.push_back(f);n /= f;}}results.push_back(factors); // add factorization to results});// end of parallel calculations// find largest minimal prime factor in resultsauto max = std::max_element(results.begin(), results.end(), [](const Factors &a, const Factors &b){
return a.primes.front() < b.primes.front();});// print number(s) and factorizationstd::for_each(results.begin(), results.end(), [&](const Factors &f){
if (f.primes.front() == max->primes.front()){
std::cout << f.number << " = [ ";std::copy(f.primes.begin(), f.primes.end(), std::ostream_iterator<int>(std::cout, " "));std::cout << "]\n";}});return 0;
}
输出：
12878611 = [ 47 101 2713 ]
12878893 = [ 47 274019 ]
Go
package mainimport ("fmt""math/big"
)// collection of numbers. A slice is used for the collection.
// The elements are big integers, since that's what the function Primes
// uses (as was specified by the Prime decomposition task.)
var numbers = []*big.Int{
big.NewInt(12757923),big.NewInt(12878611),big.NewInt(12878893),big.NewInt(12757923),big.NewInt(15808973),big.NewInt(15780709),
}// main just calls the function specified by the task description and
// prints results. note it allows for multiple numbers with the largest
// minimal factor. the task didn't specify to handle this, but obviously
// it's possible.
func main() {
rs := lmf(numbers)fmt.Println("largest minimal factor:", rs[0].decomp[0])for _, r := range rs {
fmt.Println(r.number, "->", r.decomp)}
}// this type associates a number with it's prime decomposition.
// the type is neccessary so that they can be sent together over
// a Go channel, but it turns out to be convenient as well for
// the return type of lmf.
type result struct {
number *big.Intdecomp []*big.Int
}// the function specified by the task description, "largest minimal factor."
func lmf([]*big.Int) []result {
// construct result channel and start a goroutine to decompose each number.// goroutines run in parallel as CPU cores are available.rCh := make(chan result)for _, n := range numbers {
go decomp(n, rCh)}// collect results. <-rCh returns a single result from the result channel.// we know how many results to expect so code here collects exactly that// many results, and accumulates a list of those with the largest// minimal factor.rs := []result{
<-rCh}for i := 1; i < len(numbers); i++ {
switch r := <-rCh; r.decomp[0].Cmp(rs[0].decomp[0]) {
case 1:rs = rs[:1]rs[0] = rcase 0:rs = append(rs, r)}}return rs
}// decomp is the function run as a goroutine. multiple instances of this
// function will run concurrently, one for each number being decomposed.
// it acts as a driver for Primes, calling Primes as needed, packaging
// the result, and sending the packaged result on the channel.
// "as needed" turns out to mean sending Primes a copy of n, as Primes
// as written is destructive on its argument.
func decomp(n *big.Int, rCh chan result) {
rCh <- result{
n, Primes(new(big.Int).Set(n))}
}// code below copied from Prime decomposition task
var (ZERO = big.NewInt(0)ONE = big.NewInt(1)
)func Primes(n *big.Int) []*big.Int {
res := []*big.Int{
}mod, div := new(big.Int), new(big.Int)for i := big.NewInt(2); i.Cmp(n) != 1; {
div.DivMod(n, i, mod)for mod.Cmp(ZERO) == 0 {
res = append(res, new(big.Int).Set(i))n.Set(div)div.DivMod(n, i, mod)}i.Add(i, ONE)}return res
}
输出：
largest minimal factor: 47
12878611 -> [47 101 2713]
12878893 -> [47 274019]
Java
//Java version 8
import static java.lang.System.out;
import static java.util.Arrays.stream;
import static java.util.Comparator.comparing;public interface ParallelCalculations {
public static final long[] NUMBERS = {
12757923,12878611,12878893,12757923,15808973,15780709,197622519};public static void main(String... arguments) {
stream(NUMBERS).unordered().parallel().mapToObj(ParallelCalculations::minimalPrimeFactor).max(comparing(a -> a[0])).ifPresent(res -> out.printf("%d has the largest minimum prime factor: %d%n",res[1],res[0]));}public static long[] minimalPrimeFactor(long n) {
for (long i = 2; n >= i * i; i++) {
if (n % i == 0) {
return new long[]{
i, n};}}return new long[]{
n, n};}
}
输出：
12878611 has the largest minimum prime factor: 47
Kotlin
// version 1.1.51import java.util.stream.Collectors/* returns the number itself, its smallest prime factor and all its prime factors */
fun primeFactorInfo(n: Int): Triple<Int, Int, List<Int>> {
if (n <= 1) throw IllegalArgumentException("Number must be more than one")if (isPrime(n)) return Triple(n, n, listOf(n))val factors = mutableListOf<Int>()var factor = 2var nn = nwhile (true) {
if (nn % factor == 0) {
factors.add(factor)nn /= factorif (nn == 1) return Triple(n, factors.min()!!, factors)if (isPrime(nn)) factor = nn}else if (factor >= 3) factor += 2else factor = 3}
}fun isPrime(n: Int) : Boolean {
if (n < 2) return falseif (n % 2 == 0) return n == 2if (n % 3 == 0) return n == 3var d = 5while (d * d <= n) {
if (n % d == 0) return falsed += 2if (n % d == 0) return falsed += 4}return true
}fun main(args: Array<String>) {
val numbers = listOf(12757923, 12878611, 12878893, 12757923, 15808973, 15780709, 197622519)val info = numbers.stream().parallel().map {
primeFactorInfo(it) }.collect(Collectors.toList())val maxFactor = info.maxBy {
it.second }!!.secondval results = info.filter {
it.second == maxFactor }println("The following number(s) have the largest minimal prime factor of $maxFactor:")for (result in results) {
println(" ${
result.first} whose prime factors are ${
result.third}")}
}
输出：
The following number(s) have the largest minimal prime factor of 47:12878611 whose prime factors are [47, 101, 2713]12878893 whose prime factors are [47, 274019]
Python
Python3的并发模块concurrent.futures
from concurrent import futures
from math import floor, sqrtNUMBERS = [112272537195293,112582718962171,112272537095293,115280098190773,115797840077099,1099726829285419]
# NUMBERS = [33, 44, 55, 275]def lowest_factor(n, _start=3):if n % 2 == 0:return 2search_max = int(floor(sqrt(n))) + 1for i in range(_start, search_max, 2):if n % i == 0:return ireturn ndef prime_factors(n, lowest):pf = []while n > 1:pf.append(lowest)n //= lowestlowest = lowest_factor(n, max(lowest, 3))return pfdef prime_factors_of_number_with_lowest_prime_factor(NUMBERS):with futures.ProcessPoolExecutor() as executor:low_factor, number = max( (l, f) for l, f in zip(executor.map(lowest_factor, NUMBERS), NUMBERS) )all_factors = prime_factors(number, low_factor)return number, all_factorsdef main():print('For these numbers:')print('\n '.join(str(p) for p in NUMBERS))number, all_factors = prime_factors_of_number_with_lowest_prime_factor(NUMBERS)print(' The one with the largest minimum prime factor is {}:'.format(number))print(' All its prime factors in order are: {}'.format(all_factors))if __name__ == '__main__':main()
输出：
For these numbers:1122725371952931125827189621711122725370952931152800981907731157978400770991099726829285419The one with the largest minimum prime factor is 115797840077099:All its prime factors in order are: [544651, 212609249]
通用形式
import multiprocessing# ========== #Python3 - concurrent
from math import floor, sqrtnumbers = [112272537195293,112582718962171,112272537095293,115280098190773,115797840077099,1099726829285419]
# numbers = [33, 44, 55, 275]def lowest_factor(n, _start=3):if n % 2 == 0:return 2search_max = int(floor(sqrt(n))) + 1for i in range(_start, search_max, 2):if n % i == 0:return ireturn ndef prime_factors(n, lowest):pf = []while n > 1:pf.append(lowest)n //= lowestlowest = lowest_factor(n, max(lowest, 3))return pf
# ========== #Python3 - concurrentdef prime_factors_of_number_with_lowest_prime_factor(numbers):pool = multiprocessing.Pool(processes=5)factors = pool.map(lowest_factor,numbers)low_factor,number = max((l,f) for l,f in zip(factors,numbers))all_factors = prime_factors(number,low_factor)return number,all_factorsif __name__ == '__main__':print('For these numbers:')print('\n '.join(str(p) for p in numbers))number, all_factors = prime_factors_of_number_with_lowest_prime_factor(numbers)print(' The one with the largest minimum prime factor is {}:'.format(number))print(' All its prime factors in order are: {}'.format(all_factors))