Algorithme pour trouver le plus petit nombre avec un nombre donné de facteurs
-
28-10-2019 - |
Question
Quel est l'algorithme le plus efficace auquel on puisse penser, étant donné un nombre naturel n , renvoie le plus petit nombre naturel x avec n positifdiviseurs (y compris 1 et x )?Par exemple, étant donné 4, l'algorithme devrait donner 6 (diviseurs: 1, 2, 3, 6);c'est-à-dire que 6 est le plus petit nombre ayant 4 facteurs distincts.De même, étant donné 6, l'algorithme devrait donner 12 (diviseurs: 1,2,3,4,6,12);c'est-à-dire que 12 est le plus petit nombre ayant 6 facteurs distincts
En termes de performances réelles, je recherche un algorithme évolutif capable de donner des réponses de l'ordre de 10 20 en 2 secondes sur une machine qui peut faire 10 7 calculs par seconde.
La solution
http://www.primepuzzles.net/problems/prob_019.htm
b) Jud McCranie, T.W.A. Baumann & Enoch Haga ont envoyé fondamentalement la même chose procédure pour trouver N (d) pour un d: donné
- Factoriser d comme un produit de ses diviseurs premiers: d= p 1 a 1 * p 2 a 2 * p 3 a 3 * ...
- convertir cette factorisation en une autre factorisation arithmétiquement équivalente, composée de décroissant monotone non alimenté et non facteurs premiers nécessaires ... (uf! ...) d= p 1 a 1 * p 2 < / sub> a 2 * p 3 a 3 * ...= b 1 * b 2 * b 3 ... tel que b 1 ≥ b 2 ≥ b 3 ...
Vous devez comprendre que pour chaqued
donné, il y a plusieurs factorisations équivalentes en arithmétique réalisables: par exemple:
si d= 16= 2 4 alors il y a 5 factorisations équivalentes: d= 2 * 2 * 2 * 2= 4 * 2 * 2= 4 * 4= 8 * 2= 16- N est le nombre minimal résultant du calcul de 2 b 1 -1 * 3 b 2 -1 * 5 b 3 -1 * ... pour toutes les factorisations équivalentes de d. < / em> Utilisation du même exemple:
N (16)= le minimum de ces {2 * 3 * 5 * 7, 2 3 * 3 * 5, 2 3 * 3 3 , 2 7 * 3, 2 15 }= 2 3 * 3 * 5= 120
Mise à jour: Avec des nombres autour de 10 20 , faites attention aux notes de Christian Bau citées sur la même page.
Autres conseils
//What is the smallest number with X factors?
function smallestNumberWithThisManyFactors(factorCount) {
Number.prototype.isPrime = function() {
let primeCandidate = this;
if(primeCandidate <= 1 || primeCandidate % 1 !== 0) return false
let i = 2;
while(i <= Math.floor(Math.sqrt(primeCandidate))){
if(primeCandidate%i === 0) return false;
i++;
}
return true;
}
Number.prototype.nextPrime = function() {
let currentPrime = this;
let nextPrimeCandidate = currentPrime + 1
while(nextPrimeCandidate < Infinity) {
if(nextPrimeCandidate.isPrime()){
return nextPrimeCandidate;
} else {
nextPrimeCandidate++;
}
}
}
Number.prototype.primeFactors = function() {
let factorParent = this;
let primeFactors = [];
let primeFactorCandidate = 2;
while(factorParent !== 1){
while(factorParent % primeFactorCandidate === 0){
primeFactors.push(primeFactorCandidate);
factorParent /= primeFactorCandidate;
}
primeFactorCandidate = primeFactorCandidate.nextPrime();
}
return primeFactors;
}
Number.prototype.factors = function() {
let parentNumber = this.valueOf();
let factors = []
let iterator = parentNumber % 2 === 0 ? 1 : 2
let factorCandidate = 1;
for(factorCandidate; factorCandidate <= Math.floor(parentNumber/2); factorCandidate += iterator) {
if(parentNumber % factorCandidate === 0) {
factors.push(factorCandidate)
}
}
factors.push(parentNumber)
return factors
}
Array.prototype.valueSort = function() {
return this.sort(function (a,b){ return a-b })
}
function clone3DArray(arrayOfArrays) {
let cloneArray = arrayOfArrays.map(function(arr) {
return arr.slice();
});
return cloneArray;
}
function does3DArrayContainArray(arrayOfArrays, array){
let aOA = clone3DArray(arrayOfArrays);
let a = array.slice(0);
for(let i=0; i<aOA.length; i++){
if(aOA[i].sort().join(',') === a.sort().join(',')){
return true;
}
}
return false;
}
function removeDuplicateArrays(combinations) {
let uniqueCombinations = []
for(let c = 0; c < combinations.length; c++){
if(!does3DArrayContainArray(uniqueCombinations, combinations[c])){
uniqueCombinations[uniqueCombinations.length] = combinations[c];
}
}
return uniqueCombinations;
}
function generateCombinations(parentArray) {
let generate = function(n, src, got, combinations) {
if(n === 0){
if(got.length > 0){
combinations[combinations.length] = got;
}
return;
}
for (let j=0; j<src.length; j++){
generate(n - 1, src.slice(j + 1), got.concat([src[j]]), combinations);
}
return;
}
let combinations = [];
for(let i=1; i<parentArray.length; i++){
generate(i, parentArray, [], combinations);
}
combinations.push(parentArray);
return combinations;
}
function generateCombinedFactorCombinations(primeFactors, primeFactorCombinations) {
let candidates = [];
for(let p=0; p<primeFactorCombinations.length; p++){
let product = 1;
let primeFactorsCopy = primeFactors.slice(0);
for(let q=0; q<primeFactorCombinations[p].length; q++){
product *= primeFactorCombinations[p][q];
primeFactorsCopy.splice(primeFactorsCopy.indexOf(primeFactorCombinations[p][q]), 1);
}
primeFactorsCopy.push(product);
candidates[candidates.length] = primeFactorsCopy.valueSort().reverse();
}
return candidates;
}
function determineMinimumCobination (candidates){
let minimumValue = Infinity;
let bestFactorCadidate = []
for(let y=0; y<candidates.length; y++){
let currentValue = 1;
let currentPrime = 2;
for(let z=0; z<combinedFactorCandidates[y].length; z++){
currentValue *= Math.pow(currentPrime,(combinedFactorCandidates[y][z])-1);
currentPrime = currentPrime.nextPrime();
}
if(currentValue < minimumValue){
minimumValue = currentValue;
bestFactorCadidate = combinedFactorCandidates[y];
}
}
return minimumValue;
}
let primeFactors = factorCount.primeFactors();
let primeFactorCombinations = removeDuplicateArrays(generateCombinations(primeFactors));
let combinedFactorCandidates = generateCombinedFactorCombinations(primeFactors, primeFactorCombinations);
let smallestNumberWithFactorCount = determineMinimumCobination(combinedFactorCandidates);
console.log('The smallest number with ' + factorCount + ' factors is: ')
console.log(smallestNumberWithFactorCount)
console.log('With these factors being: ')
console.log(smallestNumberWithFactorCount.factors())
return smallestNumberWithFactorCount;
}
smallestNumberWithThisManyFactors(10)