nième nombre ayant n nombre de facteurs premiers distincts

10

Créez la fonction, le programme ou l'expression la plus courte qui calcule A073329 , c'est-à- a(n)dire le nième nombre ayant n facteurs premiers distincts. L'entrée est le nombre d'éléments de la séquence à renvoyer. 0 < n. Je ne suis pas concerné par la précision entière. Je veux juste l'algorithme. Pour les langues qui ne prennent pas en charge des entiers arbitrairement grands, nous prétendons simplement qu'elles le font.

Vous pouvez trouver des cas de test en suivant le lien vers OEIS ci-dessus.

MISE À JOUR:

Permettez-moi de préciser que vous devez renvoyer une séquence entière à partir de votre programme, fonction ou expression. En d'autres termes, f(x)devrait calculer a(n)pour tous nde 1 à x. Étant donné x8, votre fonction devrait retourner 2, 10, 60, 420, 4290, 53130, 903210, 17687670sous forme de tableau ou d'une autre structure de données appropriée.

Gregory Higley
la source
Limites / limites ??
st0le
Je ne suis pas vraiment préoccupé par les limites et les limites, mais si c'est important pour vous, faites l'algorithme en supposant que l'entrée ne sera pas supérieure à 8, et nous prétendrons que cela fonctionne pour des nombres plus élevés. Comme je l'ai dit, je m'intéresse à l'algorithme mathématique abstrait, pas aux détails des limitations entières d'un langage particulier.
Gregory Higley
1
Peut-être que c'est plus ouvert, quand on dit: output a(1), ... a(n)au lieu de retourner quelque chose, comme un tableau de ...
utilisateur inconnu

Réponses:

2

Python, 144 caractères

R=range
P=[x for x in R(2,99)if all(x%i for i in R(2,x))]
for a in R(input()):
 x=n=0
 while n<=a:n+=sum(x%p==0for p in P)==a+1;x+=1
 print x-1

Il faut environ 2 minutes pour terminer jusqu'à x = 8.

Keith Randall
la source
2

Java, 170 caractères sur une ligne

int a(int n) {
    int a = 2, t = a, m = 1, i = 1;
    Set s = new HashSet();
    while (i++ > 0) {
        if (t % i == 0) {
            s.add(i);
            t /= i;
            if (t == 1) {
                if (s.size() == n) {
                    if (n == m) {
                        break;
                    }
                    m++;
                }
                t = ++a;
                s.clear();
            }
            i = 1;
        }
    }
    return a;
}

Mise à jour, +77 caractères IOL

int[] f(int n) {
    int[] f = new int[n];
    for (int i = 0; i < n; i++) {
        f[i] = a(i+1);
    }
    return f;
}
cubanacan
la source
C'est en fait incorrect, mais proche, bien que je pense que je devrais peut-être clarifier ma question. Vous devez renvoyer une séquence entière. Par exemple, si l'entrée 8, vous devez renvoyer les 8 premiers éléments de la séquence A073329.
Gregory Higley
@Gregory regarde la mise à jour
cubanacan
Je suis désolé - je vous ai voté contre, sur la base de ma propre mauvaise compréhension de la tâche, qui a clarifié après avoir lu le lien OEIS. Si vous effectuez une modification mineure de votre message, je peux et révoquerai mon downvote.
utilisateur inconnu
@user en raison de ma propre incompréhension de votre commentaire, clarifiez votre demande, s'il vous plaît
cubanacan
J'ai mal compris la question et j'ai pensé que tous les facteurs doivent être des nombres premiers distincts, donc 2 * 3 * 5 * 2 serait une mauvaise réponse. J'ai donc rejeté votre réponse parce qu'elle était fausse. Ensuite, j'ai découvert comment les «nombres premiers distincts» doivent être compris et j'ai voulu corriger mon vote, mais je n'ai pas le droit de changer mon vote - ce n'est possible que dans les premières minutes. Mais si vous modifiez votre réponse, je peux changer mon vote. Je vous demande donc de modifier un peu.
utilisateur inconnu
2

Java (non golfé)

public class M {

    public static void main(String[] a) {
        final int N = 100000000;
        int[] p = new int[N];
        for(int f = 2; f * f < N; f++) {
            if(p[f] == 0)
                for(int k = f; k < N; k += f)
                    p[k]++;
        }
        for(int i = 1; i <= 8; i++) {
            int c = 0, j;
            for(j = 1; j < N && c < i; j++)
                if(p[j] == i)
                    c++;
            if(c == i)
                System.out.println(i + " = " + --j);
        }
    }
}

Utilise un algorithme de tamisage. C'est assez rapide. (6 secondes) fonctionnera avec précision pendant jusqu'à 8, échouera probablement pour quelque chose de plus élevé.

st0le
la source
1

JavaScript, 149 caractères

function(n){function f(x){for(r=[],o=x,z=2;z<=o;x%z?++z:(x/=z,r.indexOf(z)+1?0:r.push(z)));return r}for(c=0,i=1;c<n;)f(++i).length==n?c++:0;return i}

Ne répond pas pour n> = 6, donc je n'ai pas testé combien de temps cela prend (mon navigateur affiche une notification de script bloqué toutes les 10 secondes environ donc je ne peux pas le chronométrer avec précision et je ne veux pas me bloquer complètement si je cochez "ne plus afficher cela" ...)

Edit: Pour renvoyer le tableau est de 200 caractères (+51) :

function(n){function F(){function f(x){for(r=[],o=x,z=2;z<=o;x%z?++z:(x/=z,r.indexOf(z)+1?0:r.push(z)));return r}for(c=0,i=1;c<n;)F(++i).length==n?c++:0;return i}for(a=[];n>0;n--)a.push(f());return a}
Ry-
la source
0

J, 32 octets

({"0 1~i.@#)(]/.~#@~.@q:)

Mais comme je réponds à ma propre question si tard, nous allons simplement laisser cette réponse comme une curiosité.

Gregory Higley
la source