n-е число, имеющее n число различных простых факторов

10

Создайте самую короткую функцию, программу или выражение, которое вычисляет A073329 , т. Е.a(n) Является n-м числом, имеющим n различных простых множителей. Ввод - это количество элементов в последовательности, которое нужно вернуть. 0 < n, Я не обеспокоен целочисленной точностью. Я просто хочу алгоритм. Для языков, которые не поддерживают произвольно большие целые числа, мы просто притворимся, что они делают.

Вы можете найти контрольные примеры, перейдя по ссылке на OEIS, приведенной выше.

ОБНОВИТЬ:

Позвольте мне прояснить, что вам нужно возвращать целочисленную последовательность из вашей программы, функции или выражения. Другими словами, f(x)следует рассчитывать a(n)для всех nот 1 до x. Учитывая x8, ваша функция должна возвращаться 2, 10, 60, 420, 4290, 53130, 903210, 17687670в виде массива или другой подходящей структуры данных.

code-golf math Грегори Хигли
источник
Пределы / оценки ??
st0le
Меня не очень интересуют ограничения и границы, но если это важно для вас, сделайте алгоритм, предполагая, что ввод будет не более 8, и мы притворимся, что он работает для больших чисел. Как я уже сказал, меня интересует абстрактный математический алгоритм, а не детали целочисленных ограничений конкретного языка.
Грегори Хигли
1
Может быть, это более открыто, когда мы говорим: output a(1), ... a(n)вместо того, чтобы возвращать что-то, как массив ...
пользователь неизвестен

Ответы:

2

Питон, 144 символа

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

Требуется приблизительно 2 минуты, чтобы закончиться для x = 8.

Кит Рэндалл
источник
2

Java, 170 символов в одну строку

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;
}

Обновление, +77 символов 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
источник
Это на самом деле неправильно, но близко, хотя я думаю, что, возможно, мне следует прояснить свой вопрос. Вы должны возвращать целочисленную последовательность. Например, если вход 8, вы должны вернуть первые 8 элементов в последовательности A073329.
Грегори Хигли
@ Грегори, посмотрите на обновление
кубанакан
Извините, я проголосовал за вас, исходя из собственного недопонимания задачи, которое выяснилось после прочтения ссылки OEIS. Если вы сделаете небольшую правку своего поста, я могу и отзову мое понижение.
пользователь неизвестен
@ Пользователь из-за моего собственного недопонимания вашего комментария, пожалуйста, уточните ваш запрос
cubanacan
Я неправильно понял вопрос и подумал, что все факторы должны быть различными простыми числами, поэтому 2 * 3 * 5 * 2 будет неправильным ответом. Поэтому я проголосовал за твой ответ за то, что был ложным. Затем я обнаружил, как понимать «отдельные простые числа», и хотел исправить свое голосование, но мне не разрешено менять свой голос - это возможно только в первые несколько минут. Но если вы отредактируете свой ответ, я могу изменить свой голос. Поэтому я прошу вас немного отредактировать.
пользователь неизвестен
2

Ява (Ungolfed)

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);
        }
    }
}

Использует алгоритм сита. Это довольно быстро. (6 секунд) Точно сработает для upto 8, вероятно, потерпит неудачу для чего-то более высокого.

st0le
источник
1

JavaScript, 149 символов

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}

Чувствует себя не отвечающим при n> = 6, поэтому я не проверял, сколько времени это занимает (мой браузер выдает уведомление о зависшем скрипте каждые 10 секунд или около того, поэтому я не могу точно рассчитать время и не хочу полностью зависать, если я отметьте "не показывать это снова" ...)

Изменить: Чтобы вернуть массив составляет 200 символов (+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}
Рыбаковым
источник
0

J, 32 байта

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

Но так как я отвечаю на свой собственный вопрос так поздно, мы просто оставим этот ответ из любопытства.

Грегори Хигли
источник