Faktor prima tertinggi dari angka tetangga

13

Saya pikir paling mudah untuk menjelaskan tantangan ini secara berurutan. Mulai dengan nomor input N dan:

  1. Temukan faktor prima tertinggi
  2. Memeriksa nomor di atas dan di bawah N dan melihat apakah faktor utama tertinggi adalah lebih tinggi (yaitu faktor utama tertinggi N-1 dan / atau N + 1 lebih tinggi dari faktor N .
  3. Lanjutkan untuk memeriksa angka yang lebih tinggi dan / atau lebih rendah tetangga N dalam arah di mana faktor tertinggi meningkat ( (N-2, N-3 ...) dan / atau (N + 2, N + 3 ...) dan sebagainya di)
  4. Setelah tidak ada faktor prima di kedua arah yang lebih tinggi dari yang telah kami temukan, kami berhenti dan menampilkan faktor prima tertinggi yang kami temui.

Mari kita lihat sebuah contoh:

245memiliki faktor utama 5, 7, 7. Tetangganya adalah:

244 -> 2,  2,  61
245 -> 5,  7,  7
246 -> 2,  3,  41

Faktor prima tertinggi meningkat di kedua arah, jadi kita harus melihat tetangga berikutnya:

243 -> 3,   3,  3,  3,  3
244 -> 2,   2,  2,  61
245 -> 5,   7,  7
246 -> 2,   3,  41
247 -> 13,  19

Faktor prima tertinggi sekarang menurun di kedua arah, sehingga faktor prima tertinggi yang kami temui adalah 61, dan karenanya harus dikembalikan.

Contoh lain:

Mari lihat 1024. Faktor utamanya adalah 2, 2, 2, 2, 2, 2, 2, 2, 2, 2. Faktor utama tetangga terdekatnya adalah:

1023 -> 3, 11, 31
1024 -> 2,  2,  2,  2,  2,  2,  2,  2,  2,  2
1025 -> 5,  5, 41

Faktor prima tertinggi meningkat di kedua arah, dari 2ke 31atau 41. Mari kita lihat tetangga:

1022 -> 2, 7,  73
1023 -> 3, 11, 31
1024 -> 2,  2,  2,  2,  2,  2,  2,  2,  2,  2
1025 -> 5,  5, 41
1026 -> 2,  3,  3, 19

Faktor prima tertinggi 1022adalah 73, dan faktor prima tertinggi 1026adalah 19. Karena 19lebih rendah daripada 41kita tidak tertarik. Angka ini masih bertambah untuk angka yang lebih kecil dari N, jadi kami akan memeriksa yang berikutnya ke arah itu :

1021 -> 1021
1022 -> 2, 7,  73
1023 -> 3, 11, 31
1024 -> 2,  2,  2,  2,  2,  2,  2,  2,  2,  2
1025 -> 5,  5, 41
1026 -> 2,  3,  3, 19

1021 adalah prime, dan prime tertinggi yang kami temui, jadi harus dikembalikan.

Aturan:

  • Anda hanya akan mendapatkan positif Nlebih besar dari1 dan lebih kecil dari 2^31-2.
  • Format input dan output adalah opsional, tetapi angkanya harus dalam basis 10.
  • Anda harus terus mencari bilangan prima yang lebih tinggi selama nilai tertinggi meningkat ke arah itu. Arahnya tidak tergantung satu sama lain.

Kasus uji:

Format: N, highest_factor

2, 3
3, 3
6, 7
8, 11
24, 23 
1000, 997
736709, 5417 
8469038, 9431
code-golf math primes Stewie Griffin
sumber
Katakanlah kita mendapatkan faktor prima tertinggi 2untuk N. Kita kemudian mendapatkan 5untuk N-1 dan 61untuk N +1. Lalu kita dapatkan 19untuk N-2 dan 67untuk N + 2. Haruskah kita terus mencoba angka yang lebih rendah, sejak 19>5atau berhenti, sejak 5<61? Yaitu maksima disimpan per-sisi? (Saya tidak yakin apakah contohnya secara matematis dimungkinkan.)
PurkkaKoodari
@ Pietu1998, apakah pertanyaannya lebih jelas sekarang?
Stewie Griffin
N=2sebenarnya tampaknya menjadi tepi kasus karena 1tidak memiliki faktor prima, jadi tidak ada faktor prima maksimum yang dapat kita bandingkan untuk memutuskan apakah kita harus melanjutkan.
Jonathan Allan

Jawaban:

4

Mathematica, 82 74 byte

Terima kasih kepada Martin Ender karena telah menghemat 8 byte!

Max@@(±n_:=#//.x_/;l[t=x+n]>l@x:>t;l=FactorInteger[#][[-1,1]]&)/@{±-1,±1}&

Fungsi tanpa nama mengambil input integer dan mengembalikan integer.

±n_:=#//.x_/;l[t=x+n]>l@x:>tmendefinisikan fungsi unary ±yang terus meningkatkan input integer fungsi global nselama faktor prima terbesar meningkat. (Fungsi faktor prima terbesar didefinisikan dengan l=FactorInteger[#][[-1,1]]&.) {±-1,±1}Oleh karena itu berlaku fungsi itu dua kali untuk bilangan bulat input, dengan kenaikan -1dan lagi dengan kenaikan 1. Kemudian,Max@@(...l...)/@... ambil yang lebih besar dari dua faktor prima terbesar yang ditemukan.

Pengajuan sebelumnya:

Max@@(l=FactorInteger[#][[-1,1]]&)/@(#//.x_/;l[t=x+#2]>l[x]:>t&@@@{{#,-1},{#,1}})&
Greg Martin
sumber
Menyimpan beberapa byte dengan menghindari @@@(dan Anda dapat menggunakannya di l@xsana):Max@@(±n_:=#//.x_/;l[t=x+n]>l@x:>t;l=FactorInteger[#][[-1,1]]&)/@{±-1,±1}&
Martin Ender
1

Perl, 137 byte

122 byte kode + 15 byte untuk -pdan -Mntheory=:all.

sub f{$t=(factor$_+pop)[-1]}$i=$j=1;while($i|$j){f++$c;($i&=$t>$h)&&($h=$t);f-$c;($j&=$t>$l)&&($l=$t)}$_=$h>$l?$h:$l?$l:$_

Untuk menjalankannya:

perl -pMntheory=:all -e 'sub f{$t=(factor$_+pop)[-1]}$i=$j=1;while($i|$j){f++$c;($i&=$t>$h)&&($h=$t);f-$c;($j&=$t>$l)&&($l=$t)}$_=$h>$l?$h:$l?$l:$_' <<< 736709

Jika Anda belum ntheorymenginstal, Anda dapat menginstalnya dengan mengetik (echo y;echo) | perl -MCPAN -e 'install ntheory'di terminal Anda.

Dada
sumber
0

Ruby, 99 byte

->n{f=->n{i=2;n%i<1?n/=i:i+=1while i<n;n};g=->s,z{s+=z while f[s+z]>b=f[s];b};[g[n,1],g[n,-1]].max}

Penjelasan:

  • f () adalah faktor prima tertinggi
  • g () adalah fungsi mencari tetangga dalam satu arah
  • berlaku g to (n, -1) dan to (n, + 1) untuk mencari di kedua arah
GB
sumber