26

Удивительно, но я не думаю, что у нас есть вопрос по коду для определения, является ли число полупростым .

Полупростое число - это натуральное число, являющееся произведением двух (не обязательно различных) простых чисел.

Достаточно простая, но удивительно важная концепция.

Учитывая положительное целое число, определите, является ли оно полупростым. Ваш вывод может быть в любой форме, при условии, что он дает одинаковый вывод для любого истинного или ложного значения. Вы также можете предположить, что ваш ввод достаточно мал, чтобы производительность или переполнение не были проблемой.

Тестовые случаи:

input -> output
1     -> false
2     -> false
3     -> false
4     -> true
6     -> true
8     -> false
30    -> false   (5 * 3 * 2), note it must be EXACTLY 2 (non-distinct) primes
49    -> true    (7 * 7)      still technically 2 primes
95    -> true
25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357
      -> true, and go call someone, you just cracked RSA-2048

Это код-гольф , поэтому применяются стандартные правила!

code-golf sequence Лорд Фаркуаад
источник

4

@WheatWizard Есть небольшая разница в том, что требуется 3 простых числа (не большая разница почти для всех языков), и это только для отдельных простых чисел (довольно отличающихся для некоторых языков). Я могу обсудить это с вами в чате, если вы хотите продолжить более подробное обсуждение.

HyperNeutrino

2

@WheatWizard Вы подняли хороший вопрос, но, аналогично, у нас уже есть куча разных типов вопросов, и хотя, в отличие от того, что вы выражаете, большинство из них вносят значительный вклад в их область, этот вопрос имеет достаточно различий что я считаю, что это требует отдельного вопроса / поста.

HyperNeutrino

2

@hyperneutrino, глядя на ответы на оба вопроса, похоже, что разница в исходном коде - одно число, 2 против 3. Я бы вряд ли назвал это большой разницей.

Пшеничный волшебник

2

@WheatWizard Также есть «разные» и «не отличные» ...

HyperNeutrino

3

@LordFarquaad Только потому, что его дубликат не означает, что это плохо. Я считаю, что дублирование - это хорошая вещь, это означает, что вы спрашиваете о вещах, которые сообщество находит достаточно интересными, чтобы о них уже спрашивали.

Пшеничный волшебник

19

Брахилог , 2 байта

В основном это порт от ответа Фатализ на вызов Сфенического числа.

ḋĊ

Попробуйте онлайн!

Как?

ḋĊ - implicitly takes input
ḋ  - prime factorisation (with duplicates included)
 Ċ - is a couple

Джонатан Аллан
источник

1

Действительно правильный язык для работы: P

HyperNeutrino

2

@Uriel Ċ- это встроенный список двух переменных; Будучи декларативным языком, по умолчанию вывод является тестом на удовлетворение (например, сам ḋпо себе будет выводить true.для неотрицательных целых чисел).

Джонатан Аллан

Как это 2 байта?

Harold

1

@harold Я только что обновил, чтобы сделать "байты" в заголовке ссылки на кодовую страницу Brachylog. Шестнадцатеричный дамп будет c6 eb.

Джонатан Аллан

16

Шелуха , 4 байта

_{Смотри ма не Юникод!}

=2Lp

Попробуйте онлайн!

Как?

=2Lp - a one input function
   p - prime factorisation (with duplicates included)
  L  - length
=2   - equals 2?

Джонатан Аллан
источник

8

Mathematica, 16 байтов

PrimeOmega@#==2&

PrimeOmega подсчитывает количество простых факторов, считая кратность.

ngenisis
источник

1

Черт, есть встроенный?

JungHwan Мин

1

@JungHwanMin Если бы только это былоSemiprimeQ

ngenisis

Ницца. Я не знал оPrimeOmega

DavidC

7

Pyth , 4 байта

q2lP

Тестовый пакет .

Как?

q2lPQ     - Q is implicit input.

q2        - Is equal to 2?
    lPQ   - The length of the prime factors of the input.

Мистер Xcoder
источник

Черт возьми, короче встроенные! :(

HyperNeutrino

7

Python 3 , 54 байта

lambda n:0<sum((n%x<1)+(x**3==n)for x in range(2,n))<3

Попробуйте онлайн!

^{В предыдущей версии были некоторые проблемы с округлением больших чисел куба ( 125и 343т. Д.).}
Это вычисляет количество делителей (не только простых чисел), если оно имеет 1или 2возвращает True.
Единственным исключением является случай, когда число имеет более двух простых факторов, но только два делителя. В этом случае это идеальный куб простого числа (его делителями являются его кубический корень и его кубический корень в квадрате). x**3==nбудет охватывать этот случай, добавление одного к записи корня куба увеличивает сумму до 3 и останавливает ложноположительные значения. ^{спасибо Джонатану Аллану за письмо с этим прекрасным объяснением}

прут
источник

Это утверждение 8 полупростое

xnor

n**(1/3)%1>0<sum...должно сработать.

Деннис

1

@xnor исправил это.

Род

Сделано крошечное редактирование (например, 6 кубов имеет гораздо больше делителей)

Джонатан Аллан

6

Рубин , 56 48 байтов

->x{r=c=2;0while x%r<1?(x/=r;c-=1):x>=r+=1;c==0}

Попробуйте онлайн!

Как это работает:

->x{                    # Lambda function
    r=c=2;              # Starting from r=2, c=2
    0 while             # Repeat (0 counts as a nop)
        x%r<1? (        # If x mod r == 0
            x/=r:       # Divide x by r
            c-=1        # decrease c
        ):              # else
            x>=r+=1     # increase r, terminate if r>x 
    );
    c==0                # True if we found 2 factors
}

Спасибо Value Ink за идею, которая сэкономила 8 байтов.

гигабайт
источник

Почему бы просто не cначать с 0 и не сосчитать, а не сделать массив массивом, к которому вы добавляете все факторы? Таким образом, вы size

Value Ink

Вы правы, потому что я написал функцию факторизации для другой задачи и использовал ее здесь.

GB

5

Mathematica, 31 29 байт

Tr[Last/@FactorInteger@#]==2&

Юнг Хван Мин
источник

4

Нейм , 4 байта

𝐏𝐥δ𝔼

Попробуйте онлайн!

Okx
источник

Можете ли вы объяснить, как это 4 байта? ... Я полностью сбит с толку.

Мистер Кскодер

Lol У меня только что было это

HyperNeutrino

@ Mr.Xcoder Neim имеет пользовательскую кодовую страницу

JungHwan Мин

@ Mr.Xcoder Используя кодовую Neim, это 𝐏, 𝐥, δи в 𝔼виде отдельных байтов.

HyperNeutrino

@HyperNeutrino Я только немного запутал 2, и теперь это единственный ответ без 2 :)

Okx

4

Python 2 , 67 байт

lambda k:f(k)==2
f=lambda n,k=2:n/k and(f(n,k+1),1+f(n/k,k))[n%k<1]

Попробуйте онлайн!

-10 байт благодаря @JonathanAllan!

Кредит на алгоритм факторизации Prime идет Деннису (в первоначальной версии)

Мистер Xcoder
источник

Вы использовали код из ответа Денниса ? Если это так, вы должны дать кредит.

полностью человек

1

@totallyhuman Ах да, прости. Я использовал его в двух разных ответах сегодня, и я дал ему кредит в одном из них, но я забыл сделать это здесь еще раз. Спасибо, что заметили это!

г-н Xcoder

1

67 байт

Джонатан Аллан

@JonathanAllan Wow, большое спасибо!

г-н Xcoder

55 байтов

Халвард Хаммел

4

JavaScript (ES6), 47 байт

Возвращает логическое значение.

n=>(k=1)==(d=n=>++k<n?n%k?d(n):d(n/k--)+1:0)(n)

демонстрация

Показать фрагмент кода

let f =

n=>(k=1)==(d=n=>++k<n?n%k?d(n):d(n/k--)+1:0)(n)

console.log(
  [...Array(200).keys()].filter(f).join`, `
)

Развернуть фрагмент

Arnauld
источник

4

Mathematica 32 байта

Благодаря ngenesis за 1 байт сохранено

Tr@FactorInteger[#][[;;,2]]==2&

DavidC
источник

1

Сохраните один байт, используя ;;вместо All.

нгенисис

3

Желе , 5 байт

ÆfL=2

Попробуйте онлайн!

объяснение

ÆfL=2  Main link
Æf     Prime factors
  L    Length
   =   Equals
    2  2

HyperNeutrino
источник

3

На самом деле , 4 байта

ol2=

Попробуйте онлайн!

Мистер Xcoder
источник

3

05AB1E, 4 байта

Òg2Q

Попробуйте онлайн!

Как?

Ò       prime factors list (with duplicates)
 g      length
   Q    equal to
  2     2

Уриэль
источник

3

MATL, 5 байтов

Yfn2=

Попробуйте онлайн!

объяснение

Yf - Главные факторы.
n - длина
2= - равно 2?

Мистер Xcoder
источник

3

Дьялог АПЛ, 18 байт

⎕CY'dfns'
2=≢3pco⎕

Попробуйте онлайн!

Как?

⎕CY'dfns' - импорт pco

3pco⎕- запустить pcoна входе с левым аргументом 3 (простые факторы)

2=≢ - длина = 2?

Уриэль
источник

3

Gaia , 4 байта

ḍl2=

4 байта, кажется, общая длина, интересно, почему ...: P

Попробуйте онлайн!

объяснение

ḍ     Prime factors
 l    Length
  2=  Equals 2?

Бизнес Кот
источник

4 байта, кажется, общая длина, я удивляюсь, почему ... - Возможно, потому что все ответы - простые факторы, длина равна 2?

Мистер Кскодер

@MrXcoder Да, именно

Business Cat

4 из которых мои BTW> _>

г-н Xcoder

4 также является первым полупростым. Пугающий!

Нил

3

Python с SymPy 1.1.1 , 57 44 байта

-13 байт благодаря alephalpha (используйте 1.1.1 primeomega)

from sympy import*
lambda n:primeomega(n)==2

Попробуйте онлайн!

Джонатан Аллан
источник

lambda n:primeomega(n)==2

алефальфа

Ах, это напоминает мне перейти с 1.0, спасибо!

Джонатан Аллан

3

R , 67 байт

c=0;n=scan();for(p in(1:n)[-1:-2]-1)while(n%%p<1){c=c+1;n=n/p};c==2

Попробуйте онлайн!

Дрянная Монахиня
источник

2

Рубин , 35 + 8 = 43 байта

Использует -rprimeфлаг, чтобы разблокировать prime_divisionфункцию.

->n{n.prime_division.sum(&:pop)==2}

Попробуйте онлайн!

Значение чернил
источник

2

Java 8, 69 61 байт

n->{int r=1,c=2;for(;r++<n;)for(;n%r<1;n/=r)c--;return c==0;}

-8 байт благодаря @Nevay .

Попробуй это здесь.

Кевин Круйссен
источник

1

Вы можете удалить оператор else (который может быть else++r;), чтобы сохранить 8 байтов n->{int r=1,c=2;for(;r++<n;)for(;n%r<1;n/=r)c--;return c==0;}.

17

1

Python 2 , 75 65 байт

lambda n:g(n)==2
g=lambda n,i=2:n/i and[g(n,i+1),1+g(n/i)][n%i<1]

Попробуйте онлайн!

Все заслуги перед ответом xnor за исходный основной код факторизации.

totallyhuman
источник

1

C #, 112 байт

n=>{var r=Enumerable.Range(2,n);var l=r.Where(i=>r.All(x=>r.All(y=>y*x!=i)));return l.Any(x=>l.Any(y=>y*x==n));}

С применением форматирования:

n =>
{
    var r = Enumerable.Range (2, n);
    var l = r.Where (i => r.All (x => r.All (y => y * x != i)));
    return l.Any (x => l.Any (y => y * x == n));
}

И как тестовая программа:

using System;
using System.Linq;


namespace S
{
    class P
    {
        static void Main ()
        {
            var f = new Func<int, bool> (
                n =>
                {
                    var r = Enumerable.Range (2, n);
                    var l = r.Where (i => r.All (x => r.All (y => y * x != i)));
                    return l.Any (x => l.Any (y => y * x == n));
                }
            );

            for (var i = 0; i < 100; i++)
                Console.WriteLine ($"{i} -> {f (i)}");
            Console.ReadLine ();
        }
    }
}

Который имеет выход:

0 -> False
1 -> False
2 -> False
3 -> False
4 -> True
5 -> False
6 -> True
7 -> False
8 -> False
9 -> True
10 -> True
11 -> False
12 -> False
13 -> False
14 -> True
15 -> True
16 -> False
17 -> False
18 -> False
19 -> False
20 -> False
21 -> True
22 -> True
23 -> False
24 -> False
25 -> True
26 -> True
27 -> False
28 -> False
29 -> False
30 -> False
31 -> False
32 -> False
33 -> True
34 -> True
35 -> True
36 -> False
37 -> False
38 -> True
39 -> True
40 -> False
41 -> False
42 -> False
43 -> False
44 -> False
45 -> False
46 -> True
47 -> False
48 -> False
49 -> True
50 -> False
51 -> True
52 -> False
53 -> False
54 -> False
55 -> True
56 -> False
57 -> True
58 -> True
59 -> False
60 -> False
61 -> False
62 -> True
63 -> False
64 -> False
65 -> True
66 -> False
67 -> False
68 -> False
69 -> True
70 -> False
71 -> False
72 -> False
73 -> False
74 -> True
75 -> False
76 -> False
77 -> True
78 -> False
79 -> False
80 -> False
81 -> False
82 -> True
83 -> False
84 -> False
85 -> True
86 -> True
87 -> True
88 -> False
89 -> False
90 -> False
91 -> True
92 -> False
93 -> True
94 -> True
95 -> True
96 -> False
97 -> False
98 -> False
99 -> False

MetaColon
источник

1

Пари / ГП , 17 байт

n->bigomega(n)==2

Попробуйте онлайн!

alephalpha
источник

1

Сетчатка , 45 байт

.+
$*
^(11+)(\1)+$
$1;1$#2$*
A`\b(11+)\1+\b
;

Попробуйте онлайн! Ссылка включает в себя тестовые случаи. Объяснение:

.+
$*

Преобразовать в одинарный.

^(11+)(\1)+$
$1;1$#2$*

Попробуйте найти два фактора.

A`\b(11+)\1+\b

Убедитесь, что оба фактора просты.

Убедитесь, что были найдены два фактора.

Нил
источник

1

Python 2, 90 байт

def g(x,i=2):
 while x%i:i+=1
 return i
def f(n,l=0):
 while 1%n:l+=1;n/=g(n)
 return l==2

fпринимает целое число nбольше или равно 1, возвращает логическое значение.

Попробуйте онлайн!

Тестовые случаи:

>>> f(1)
False
>>> f(2)
False
>>> f(3)
False
>>> f(4)
True
>>> f(6)
True
>>> f(8)
False
>>> f(30)
False
>>> f(49)
True
>>> f(95)
True

nog642
источник

1

J , 6 байт

5 байтов будут работать как разовые:

   2=#q: 8
0
   2=#q: 9
1

Я считаю, что мне нужно шесть, когда я определяю функцию:

   semiprime =. 2=#@q:
   (,. semiprime) 1 + i. 20
 1 0
 2 0
 3 0
 4 1
 5 0
 6 1
 7 0
 8 0
 9 1
10 1
11 0
12 0
13 0
14 1
15 1
16 0
17 0
18 0
19 0
20 0

датчанин
источник

1

Пайк , 5 байт

Pl02q

Попробуй это здесь!

Мистер Xcoder
источник

1

Japt , 6 5 байт

k Ê¥2

Протестируйте это онлайн

объяснение

Делает то же самое, что и большинство других ответов: kполучает массив простых факторов, Êполучает его длину и ¥проверяет равенство с 2.

мохнатый
источник

÷k o)jтакже работает, к сожалению, он такой же длины :-(

ETHproductions

0

Perl 6 , 43 байта

{my \f=first $_%%*,2..$_;?f&&is-prime $_/f}

Попробуйте онлайн!

fнаименьший коэффициент больше 1 входного аргумента $_, или Nilесли $_равен 1. Возвращаемое значение функции - true, если ftrue (то есть, нет Nil) И входной аргумент, деленный на коэффициент, является простым.

Если $_само число простое, то оно fбудет равно $_и $_ / fравно 1, что не является простым, поэтому формула работает и в этом случае.

Шон
источник

Полупрайм?

Ответы:

Брахилог , 2 байта

Как?

Шелуха , 4 байта

Как?

Mathematica, 16 байтов

Pyth , 4 байта

Как?

Python 3 , 54 байта

Рубин , 56 48 байтов

Как это работает:

Mathematica, 31 29 байт

Нейм , 4 байта

Python 2 , 67 байт

JavaScript (ES6), 47 байт

демонстрация

Mathematica 32 байта

Желе , 5 байт

объяснение

На самом деле , 4 байта

05AB1E, 4 байта

MATL, 5 байтов

объяснение

Дьялог АПЛ, 18 байт

Gaia , 4 байта

объяснение

Python с SymPy 1.1.1 , 57 44 байта

R , 67 байт

Рубин , 35 + 8 = 43 байта

Java 8, 69 61 байт

Python 2 , 75 65 байт

C #, 112 байт

Пари / ГП , 17 байт

Сетчатка , 45 байт

Python 2, 90 байт

J , 6 байт

Пайк , 5 байт

Japt , 6 5 байт

объяснение

Perl 6 , 43 байта