Penghitungan semiprime bebas persegi

8

Definisi

Semiprime bebas persegi adalah bilangan alami yang merupakan produk dari dua bilangan prima yang berbeda.

Tugas

Dengan diberi nomor alami n, hitung semua semiprim bebas persegi kurang dari atau sama dengan n.

Detail

Harap tulis fungsi atau prosedur yang menerima parameter integer tunggal dan menghitung semua semi-square bebas kurang dari atau sama dengan parameternya. Hitungannya harus berupa nilai balik dari panggilan fungsi atau dicetak ke STDOUT.

Mencetak gol

Jawaban dengan jumlah karakter paling sedikit menang.

Jika terjadi seri, kriteria berikut akan digunakan secara berurutan:

  1. Orang tertinggi

  2. Kompleksitas waktu terbaik

  3. Kompleksitas ruang terburuk

Contohnya

f(1)     = 0
f(62)    = 18
f(420)   = 124
f(10000) = 2600
ardnew
sumber
oeis.org/A180074 ?
Ev_genus
oops, maaf, tetapi tidak ada urutan yang tidak benar karena pembatasan kongruensi (misalnya, 35 = 5 * 7 dan 55 = 5 * 11 tidak termasuk). Saya akan menambahkan beberapa contoh solusi untuk masalah khusus ini sebentar.
ardnew
2
oeis.org/A006881
Peter Taylor
Apa yang terjadi jika suatu bahasa tidak memiliki STDOUT (seperti javascript)? Gunakan console.log?
Inkbug
@Inkbug bukankah javascript mampu mengembalikan nilai dari suatu fungsi?
ardnew

Jawaban:

7

J, 50 40 38 37 karakter

f=:3 :'+/y<:}.~.,(~:/**/)~p:i._1&p:y'

Pemakaian:

   f 1
0
   f 62
18
   f 420
124
   f 10000
2600

Dengan terima kasih kepada FUZxxl .

Uji kinerja

   showtotal_jpm_ ''[f 1[start_jpm_ ''
 Time (seconds)
┌───────┬──────┬────────┬────────┬─────┬────┬───┐
│name   │locale│all     │here    │here%│cum%│rep│
├───────┼──────┼────────┼────────┼─────┼────┼───┤
│f      │base  │0.000046│0.000046│100.0│100 │1  │
│[total]│      │        │0.000046│100.0│100 │   │
└───────┴──────┴────────┴────────┴─────┴────┴───┘
   showtotal_jpm_ ''[f 1[f 62[start_jpm_ ''
 Time (seconds)
┌───────┬──────┬────────┬────────┬─────┬────┬───┐
│name   │locale│all     │here    │here%│cum%│rep│
├───────┼──────┼────────┼────────┼─────┼────┼───┤
│f      │base  │0.000095│0.000095│100.0│100 │2  │
│[total]│      │        │0.000095│100.0│100 │   │
└───────┴──────┴────────┴────────┴─────┴────┴───┘
   showtotal_jpm_ ''[f 1[f 62[f 420[start_jpm_ ''
 Time (seconds)
┌───────┬──────┬────────┬────────┬─────┬────┬───┐
│name   │locale│all     │here    │here%│cum%│rep│
├───────┼──────┼────────┼────────┼─────┼────┼───┤
│f      │base  │0.000383│0.000383│100.0│100 │3  │
│[total]│      │        │0.000383│100.0│100 │   │
└───────┴──────┴────────┴────────┴─────┴────┴───┘
   showtotal_jpm_ ''[f 1[f 62[f 420[f 10000[start_jpm_ ''
 Time (seconds)
┌───────┬──────┬────────┬────────┬─────┬────┬───┐
│name   │locale│all     │here    │here%│cum%│rep│
├───────┼──────┼────────┼────────┼─────┼────┼───┤
│f      │base  │0.084847│0.084847│100.0│100 │4  │
│[total]│      │        │0.084847│100.0│100 │   │
└───────┴──────┴────────┴────────┴─────┴────┴───┘
   showtotal_jpm_ ''[f 1[f 62[f 420[f 10000[f 50000[start_jpm_ ''
 Time (seconds)
┌───────┬──────┬────────┬────────┬─────┬────┬───┐
│name   │locale│all     │here    │here%│cum%│rep│
├───────┼──────┼────────┼────────┼─────┼────┼───┤
│f      │base  │5.014691│5.014691│100.0│100 │5  │
│[total]│      │        │5.014691│100.0│100 │   │
└───────┴──────┴────────┴────────┴─────┴────┴───┘

Saya bukan ahli teori seperti yang terlihat di sini di masa lalu, tapi saya pikir kompleksitas waktu adalah sesuatu seperti O (n p 2 ) di mana np adalah jumlah bilangan prima hingga dan termasuk nomor input n. Ini didasarkan pada asumsi bahwa kompleksitas metode saya (menghasilkan tabel perkalian yang sangat besar) jauh melebihi kompleksitas fungsi pembangkit utama yang dibangun pada J.

Penjelasan

f=:3 :'...'mendeklarasikan kata kerja (monadik). Input ke kata kerja diwakili oleh ydalam definisi kata kerja.

p:i._1&p:yKata p:kerjanya adalah kata kerja multi-tujuan bilangan prima, dan digunakan dalam dua cara berbeda di sini: _1&p:ymengembalikan jumlah bilangan prima kurang dari yitu p:i.menghasilkan setiap dari mereka. Menggunakan 10 sebagai input:

   p:i._1&p:10
2 3 5 7

(~:/**/)~menghasilkan tabel yang saya bicarakan sebelumnya. */menghasilkan tabel perkalian, ~:/menghasilkan tabel tidak sama (untuk menghilangkan kotak) dan keduanya dikalikan bersama. Menggunakan output kami sebelumnya sebagai input:

   */~2 3 5 7
 4  6 10 14
 6  9 15 21
10 15 25 35
14 21 35 49

   ~:/~2 3 5 7
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

   (~:/**/)~2 3 5 7
 0  6 10 14
 6  0 15 21
10 15  0 35
14 21 35  0

}.~.,sekarang kita mengubah angka menjadi satu daftar, ,dapatkan nilai unik ~.dan hapus 0 di awal}.

   }.~.,(~:/**/)~2 3 5 7
6 10 14 15 21 35

y<: perbandingan dengan input asli untuk memeriksa nilai mana yang valid:

   10<:6 10 14 15 21 35
1 1 0 0 0 0

+/ dan kemudian jumlahkan itu untuk mendapatkan jawabannya.

   +/1 1 0 0 0 0
2
Gareth
sumber
Apakah Anda memiliki versi palsu dari program ini (kebohongan sebagai lawan dari diam-diam)? 13 tidak selalu memberikan kode diam-diam paling efisien.
FUZxxl
Tidak, saya tidak menggunakan 13 dalam hal ini - meskipun saya pikir saya mungkin melakukan apa yang akan dilakukan seandainya saya mencoba. Kode ini pada dasarnya: di +/-.x<}.~.,(~:/~*[*/])p:i._1&p:[x=.nmana n adalah input.
Gareth
1
Mengapa tidak hanya f=:3 :'+/-.y<}.~.,(~:/~*[*/])p:i._1&p:y'untuk 40 karakter?
FUZxxl
Terima kasih, saya bahkan tidak pernah mempertimbangkan untuk menggunakan3 :'...'
Gareth
Apakah Anda akan menerbitkan beberapa hasil penghitungan waktu sehingga kami dapat menilai efisiensi program?
DavidC
5

Mathematica 65 64 55 51 47 39

Kode

Yang berikut menghitung jumlah semiprim bebas persegi kurang dari atau sama dengan n:

FactorInteger@Range@n~Count~{a={_,1},a}

Setiap faktor semiprime bebas persegi ke dalam struktur formulir: {{p,1}{q,1}} Misalnya,

FactorInteger@221
(* out *)
{{13, 1},{17, 1}}

Rutin hanya menghitung angka dalam rentang yang diinginkan yang memiliki struktur faktor ini.


Pemakaian

n=62;
FactorInteger@Range@n~Count~{a={_,1},a}

(* out *)
18

Waktu: Semua contoh yang diberikan

FactorInteger@Range@#~Count~{a = {_, 1}, a} & /@ {1, 62, 420, 10^4} // Timing

(* out *)
{0.038278, {0, 18, 124, 2600}}

Waktu: n = 10 ^ 6

Dibutuhkan di bawah empat detik untuk menghitung jumlah semi-primes bebas persegi kurang dari atau sama dengan satu juta.

n=10^6;
FactorInteger@Range@n~Count~{a = {_, 1}, a}//Timing
(* out *)
{3.65167, 209867}
DavidC
sumber
Fantastis, solusi ringkas
ardnew
@ardnew Terima kasih. Saya menikmati tantangannya.
DavidC
Bagus! Pertanyaan: apakah karakter spasi di sekitar =dan setelah ,benar - benar diperlukan secara sintaksis?
Todd Lehman
@ToddLehman, Anda benar. Saya menghapusnya. (Mereka belum dihitung sehingga jumlah byte tetap sama.)
DavidC
4

Python, 115

r=range
p=lambda x:all(x%i for i in r(2,x))
f=lambda x:sum([i*j<=x and p(j)and p(i)for i in r(2,x)for j in r(2,i)])
grc
sumber
f=lambda x:sum([(i*j<=x)&p(j)&p(i)for i in r(2,x)for j in r(2,i)])menghemat 5 karakter.
beary605
@ beary605: Terima kasih, tapi saya pikir itu akan memakan waktu terlalu lama tanpa korsleting.
grc
memilih Anda. terlalu banyak pemikiran itertoolsdi kepalaku.
Ev_genus
4

Jelly , 7 byte

ŒcfÆf€L

Cobalah online!

Bagaimana itu bekerja

ŒcfÆf€L  Main link. Argument: n

Œc       Generate all 2-combinations of [1, ..., n], i.e., all pairs [a, b] such
         that 1 ≤ a < b ≤ n.
   Æf€   Compute the prime factorization of each k in [1, ..., n].
  f      Filter; keep only results that appear to the left and to the right.
      L  Take the length.
Dennis
sumber
Wow, Anda membuat usaha saya terlihat memalukan. Terima kasih atas ide-idenya!
Harry
3

Python (139)

from itertools import*;s=lambda n:sum(x*y<=n and x<y for x,y in product(filter(lambda x:all(x%i for i in range(2,x)),range(2,n)),repeat=2))

Harap berikan beberapa hasil sampel sehingga pesaing dapat menguji program mereka.

Ev_genus
sumber
lihat, Anda bahkan tidak perlu contoh! : ^)
ardnew
3

Ruby 82

z=->n{[*2..n].select{|r|(2...r).all?{|m|r%m>0}}.combination(2).count{|a,b|a*b<=n}}

Demo: http://ideone.com/cnm1Z

Cristian Lupascu
sumber
2

Python 139

def f(n):
 p=[];c=0
 for i in range(2,n+1):
    if all(i%x for x in p):p+=[i]
    c+=any((0,j)[i/j<j]for j in p if i%j==0 and i/j in p)
 return c
Yonguk Jeong
sumber
2

Golfscript 64

~:ß,{:§,{)§\%!},,2=},0+:©{©{1$}%\;2/}%{+}*{..~=\~*ß>+\0?)+!},,2/

Demo online di sini

Catatan: Dalam demo di atas saya mengecualikan 420dan 10000menguji kasus. Karena uji primality yang sangat tidak efisien, program tidak dapat mengeksekusi untuk input ini dalam waktu kurang dari 5 detik.

Cristian Lupascu
sumber
2

Shell, 40

#! / bin / sh

seq $ 1 | faktor | awk 'NF == 3 && $ 2! = $ 3' | wc -l

#old, 61
#seq $ 1 | faktor | awk 'BEGIN {a = 0} NF == 3 && $ 2! = $ 3 {a ++} END {print a}'

Pemakaian:

$ ./count 1
0
$ ./count 420
124
$ ./hitung 10.000
2600
$ waktu ./cnt.sh 1000000
209867

0m23.956s nyata
pengguna 0m23.601s
sys 0m0.404s
o_o
sumber
2

Jelly , 14 13 byte

RÆEḟ0⁼1,1$Ɗ€S

Cobalah online!

RÆEḟ0⁼1,1$Ɗ€S    main function:
RÆE             get the prime factorization Exponents on each of the Range from 1 to N,
          Ɗ€    apply the preceding 1-arg function composition (3 funcs in a row) to each of the prime factorizations:
                (the function is a monadic semiprime checker, as per DavidC's algorithm)
    ḟ0          check if the factors minus the zero exponents...
      ⁼1,1$      ...are equal to the list [1,1]
             S   take the Sum of those results, or number of successes!

Kritik konstruktif disambut!

Harry
sumber
2
Kombinasi ini dan Sdapat diubah menjadi penggunaan ċ(Hitung). Anda dapat menggunakan hingga 10 byte. Saya akan membiarkan Anda menyelesaikannya!
Lynn
2

Python 2/3 , 95 94 byte

lambda n:sum(map(F,range(n+1)))
F=lambda x,v=2:sum(x%i<1and(F(i,0)or 3)for i in range(2,x))==v

Cobalah online!

Diposting dalam tantangan berusia 6 tahun karena membuat rekor Python baru, IMO itu pendekatan yang cukup menarik.

Penjelasan

lambda n:sum(map(F,range(n+1)))           # Main function, maps `F` ("is it a semiprime?")
                                          #  over the range [0, n]
F=lambda x,v=2:                           # Helper function; "Does `x` factor into `v`
                                          #  distinct prime numbers smaller than itself?"
  sum(                                    # Sum over all numbers `i` smaller than `x`
    x%i<1                                 # If `i` divides `x`,
    and                                   #  then
    (F(i,0)                               #  add 1 if `i` is prime (note that `F(i,0)`
                                          #  is just a primality test for `i`!)
    or 3)                                 #  or `3` if `i` is not prime (to make `F`
                                          #  return `False`)
  for i in range(2,x))
  ==v                                     # Check if there were exactly `v` distinct prime
                                          #  factors smaller than `x`, each with
                                          #  multiplicity 1

Python 2/3 (PyPy) , 88 82 81 byte

lambda n:sum(sum(x%i<1and(x/i%i>0or 9)for i in range(2,x))==2for x in range(n+1))

Cobalah online!

Didasarkan pada golf 92-byte oleh Value Ink. PyPy diperlukan untuk menafsirkan dengan benar 0or, karena standar Python melihat ini sebagai upaya angka oktal.

ArBo
sumber
1

Stax , 8 byte

ߺ@N¬Që↔

Jalankan dan debug itu

Dibongkar, tidak diserang, dan dikomentari, sepertinya ini.

F       for 1..n run the rest of the program
  :F    get distinct prime factors
  2(    trim/pad factor list to length 2
  :*    compute product of list
  _/    integer divide by initial number (yielding 0 or 1)
  +     add to running total

Jalankan yang ini

rekursif
sumber
1

Perl 6 , 58 45 byte

Terima kasih kepada Jo King untuk -13 byte.

{+grep {3==.grep($_%%*)&&.all³-$_}o^*,1..$_}

Mengambil keuntungan dari fakta bahwa bilangan bulat dengan empat faktor adalah semiprim bebas persegi atau kubus sempurna.

Cobalah online!

bb94
sumber
45 byte
Jo King
1

Brachylog , 7 byte

{≥ḋĊ≠}ᶜ

Cobalah online!

           The output is
{    }ᶜ    the number of ways in which you could
 ≥         choose a number less than or equal to
           the input
  ḋ        such that its prime factorization
   Ċ       is length 2
    ≠      with no duplicates.
String yang tidak terkait
sumber
0

Retina , 58 byte

_
¶_$`
%(`$
$"
,,`_(?=(__+)¶\1+$)
¶1$'
)C`1(?!(__+)\1+¶)
2

Cobalah online!

Dibawa sebagai input unary dengan _tanda penghitungan

Penjelasan

Angka adalah semi-prime bebas persegi jika faktor terbesar dan terkecil, tidak termasuk dirinya sendiri dan 1, keduanya merupakan bilangan prima.

_
¶_$`

Mengambil input dan menghasilkan setiap nomor unary kurang dari atau sama dengan itu, masing-masing pada jalurnya sendiri

%(`

Kemudian, untuk setiap nomor ...

$
$"
,,`_(?=(__+)¶\1+$)
¶1$'

Temukan faktor terkecil dan terbesarnya, tidak termasuk 1 ...

)C`1(?!(__+)\1+¶)

dan hitung jumlah mereka yang prima. Karena faktor terkecil harus prima, ini mengembalikan 1 atau 2

2

Hitung jumlah total 2-an

TwiNight
sumber
0

Python 2 , 105 104 byte

lambda m:sum(reduce(lambda(a,v),p:(v*(a+(n%p<1)),v>0<n%p**2),range(2,n),(0,1))[0]==2for n in range(m+1))

Cobalah online!

1 byte thx ke squid 🦑

Chas Brown
sumber
(p*p)bisap**2
cumi
0

Ruby -rprime , 64 byte

Saya tahu bahwa ada solusi Ruby lain di sini, tapi saya tidak ingin menabraknya dengan komentar sejak dijawab pada tahun 2012 ... dan ternyata, menggunakan bendera program menghitungnya sebagai bahasa yang berbeda , jadi saya rasa ini secara teknis bukan "Ruby".

Cobalah online!

Penjelasan

->n{(1..n).count{|i|m=i.prime_division;m.size|m.sum(&:last)==2}}
->n{                                    # Anonymous lambda
    (1..n).count{|i|                    # Count all from 1 to `n` that match
                                        # the following condition
                m=i.prime_division;     # Get the prime factors of `i` as
                                        #  base-exponent pairs (e.g. [2,3])
                m.size                  # Size of factors (# of distinct primes)
                      |                 # bit-or with...
                       m.sum(&:last)    # Sum of the last elements in the pairs
                                        #  (the sum of the exponents)
                                    ==2 # Check if that equals 2 and return.
                                        # Because 2 is 0b10, the bit-or means
                                        #  that the condition is true iff both
                                        #  are either 2 or 0, but because this
                                        #  is a prime factorization, it is
                                        #  impossible to have the number of
                                        #  distinct primes or the sum of the
                                        #  exponents to equal 0 for any number
                                        #  > 1. (And for 1, size|sum == 0.)
    }                                   # End count block
}                                       # End lambda
Nilai Tinta
sumber
0

APL (NARS), karakter 26, byte 52

{≢b/⍨{(⍵≡∪⍵)∧2=≢⍵}¨b←π¨⍳⍵}

uji:

  f←{≢b/⍨{(⍵≡∪⍵)∧2=≢⍵}¨b←π¨⍳⍵}
  f 1
0
  f 9
1
  f 62
18
  f 420
124
  f 1000
288
  f 10000
2600
  f 100000
23313

ini adalah alternatif yang lebih panjang (59 karakter yang saya inginkan)

r←h w;n;t
n←4⋄r←0
n+←1⋄→0×⍳w<n⋄→2×⍳(2≠≢t)∨2≠≢∪t←πn⋄r+←1⋄→2

uji:

  h 1000000
209867
RosLuP
sumber