Zadanie c++ liczby antypierwsze

Question

Witam, ma ktos pomysl na szybsze rozwiazanie tego problemu? (link do rozwiazania przez oi, ale nie rozumiem ich wytlumaczenia).

tresc:

spr:

kod:

#include<bits/stdc++.h>
using namespace std;
int ld(int n){
	int s=0;
	for(int i=1; i*i<=n; i++){
		if(n%i==0){
			s++;
			if(n/i!=i) s++;
		}
	}
	return s;
}
int main(){
	ios::sync_with_stdio(0);
	int n,maxi=0,l; cin>>n;
	for(int i=1; i<=n; i++){
		if(ld(i)>maxi){
			maxi=ld(i);
			l=i;
		}
	}
	cout<<l;
}

Testy

Zadanie testowane było na zestawie 21 danych testowych.

• ant1.in - n = 1, wynik: 1;
• ant2.in - n = 3, wynik: 2;
• ant3.in - n = 5, wynik: 4;
• ant4.in - n = 100000, wynik: 83160;
• ant5.in - n = 8, wynik: 6;
• ant6.in - n = 5041, wynik: 5040;
• ant7.in - n = 20159, wynik: 15120;
• ant8.in - n = 15120, wynik: 15120;
• ant9.in - n = 75000, wynik: 55440;
• ant10.in - n = 150000, wynik: 110880;
• ant11.in - n = 1000000, wynik: 720720;
• ant12.in - n = 3000, wynik: 2520;
• ant13.in - n = 8000000, wynik: 7207200;
• ant14.in - n = 15000000, wynik: 14414400;
• ant15.in - n = 30000, wynik: 27720;
• ant16.in - n = 60000000, wynik: 43243200;
• ant17.in - n = 110000000, wynik: 73513440;
• ant18.in - n = 354218765, wynik: 294053760;
• ant19.in - n = 600000000, wynik: 551350800;
• ant20.in - n = 1000000000, wynik: 735134400;
• ant21.in - n = 2000000000, wynik: 1396755360.

Dzięki za wszystkie komentarze i odpowiedzi :D

Answer 1

Rozwiązanie sprowadza się do znalezienia wszystkich kandydatów na liczby antypiersze (bo ich nie ma dużo), a następnie wyfiltrowanie prawdziwych liczb antypierwszych. Liczba n jest kandydatem na liczbe antypierwszę jeśli w rozkładzie na czynniki pierwsze ma następującą postać:

n = (p_1)^(a_1) * (p_2)^(a_2) * (p_3)^(a_3) * .. * (p_k)^(a_k), gdzie p_1 < p_2 < .. < p_k i a_1 >= a_2 >= .. >= a_k.

Dlaczego taka postać? Bo gdyby było takie i oraz j, że a_i < a_j to wystarczy zamienić a_i oraz a_j miejsami i dostaniemy mniejszą liczbę o tej samej liczbie dzielników.

Zatem wystarczy np. reukurencyjnie wygenerować wszystkich kandydatów i potem wybrać szukaną liczbę antypierwszą

Comments

byc moze ja czegos nie rozumiem, ale co to znaczy znalezc "kandydatow"? trzeba dokonac jakiejs wstepnej filtracji, ktora odrzuci pewne liczby, a dopiero potem rozpoczac proces sita?

po drugie co bedzie sie dzialo w fn, ktora sprawdza, czy liczba jest antypierwsza (tzn. wyjsciowa liczba ma zostac rozlozona na czynniki pierwsze, a potem sprawdzac, czy zachodzi ta zaleznosc: p_1 < p_2 < .. < p_k i a_1 >= a_2 >= .. >= a_k ? do tego potrzebna bedzie tablica, w ktorej pod indeksami beda kryly sie liczby oznaczajace wielokrotnosci jakiegos dzielnika, ktory jest liczba pierwsza a potem sprawdzac czy tablica jest nierosnaca. czy moze jest jakis szybszy sposob na napisanie kodu, ktory bedzie dzialal w ten sposob?)

---

Jest mniej wiecej tak jak mówisz. Na początku filtrujemy kandydatów, bo ich nie może być dużo. A potem z tych kandydatów wybieramy prawdziwe liczby antypierwsze. Generowanie kandydatów da się zrobić jedną funkcją rekurencyjną. Zaczynamy od najmniejszej liczby pierwszej, czyil 2. W pętli zwiększamy potęgę do której jest podniesione 2, a następnie wywołujemy się rekurencyjnie, ale tym razem dla 3, potem 5 itd. Trzeba tylko pamiętać, żę 3 musimy podnieść do potęgi mniejszej-równej niż ta, do której podnieśliśmy 2 itd.