Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Incalzire in pardoseala etapizata

Suprataxa card energie?!

Cum era nivelul de trai cam din a...

probleme cu ochelarii
 Impozite pe proprietati de anul v...

teava rezistenta panou apa calda

Acces in Curte din Drum National

Sub mobila de bucatarie si sub fr...
 Rezultat RMN

Numar circuite IPAT si prindere t...

Pareri brgimportchina.ro - teapa ...

Lucruri inaintea vremurilor lor
 Discuții despre TVR Sport HD.

Cost abonament clinica privata

Tremura toata, dar nu de la ro...

Renault Android
 

Factori primi

- - - - -
  • Please log in to reply
12 replies to this topic

#1
Baggins

Baggins

    Member

  • Grup: Members
  • Posts: 264
  • Înscris: 09.10.2014
Se dă următoarea problemă: https://www.pbinfo.r...robleme&id=1828
Îmi iese din timp pe ultimul test.
Pentru a afla redusul unui număr n dat, l-am descompus în factori primi (l-am verificat pe 2, pe 3 și apoi de la 5 am mers cu pasul 6 pentru a reduce timpul) și i-am înmulțit la variabila result.
#include <iostream>
#include <algorithm>
using namespace std;
void citire(int* x, int& n)
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> x[i];
}
void afisare(int* x, int n)
{
	for (int i = 0; i < n; i++)
		cout << x[i] << ' ';
}
int redus(int n)
{
	int result = 1;
	if (n % 2 == 0) {
		result *= 2;
		while (n % 2 == 0)
			n /= 2;
	}
	if (n % 3 == 0) {
		result *= 3;
		while (n % 3 == 0)
			n /= 3;
	}
	int f = 5;
	while (n != 1) {
		if (n % f == 0) {
			result *= f;
			while (n % f == 0)
				n /= f;
		}
		if (n % (f + 2) == 0) {
			result *= (f + 2);
			while (n % (f + 2) == 0)
				n /= (f + 2);
		}
		f += 6;
	}
	return result;
}
void inlocuire(int* x, int n)
{
	for (int i = 0; i < n; i++) {
		x[i] = redus(x[i]);
	}
}
bool descrescator(int i, int j)
{
	return i > j;
}
int main()
{
	int x[1005], n;
	citire(x, n);
	inlocuire(x, n);
	sort(x, x + n, descrescator);
	afisare(x, n);
	return 0;
}



#2
tavitu

tavitu

    Minune: HE a început să emită facturile!

  • Grup: Senior Members
  • Posts: 5,598
  • Înscris: 16.02.2009
Eu în primul rând nu aș mai împărți n la factorii primi. Nu văd rostul.

Eu unul aș afla cea mai mare valoare din x, un maxX. Aș calcula și salva toate numere prime până la radical din maxX inclusiv. Cel mai probabil în metoda inloc. Și apoi în metoda redus m-aș folosi de numerele prime salvate anterior ca să aflu ce trebuie.

Edited by tavitu, 19 May 2017 - 15:25.


#3
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,194
  • Înscris: 24.02.2007

Quote

În programele C/C++ nu se vor folosi variabile globale.

Posted Image

#4
f300

f300

    30k si ma duc

  • Grup: Senior Members
  • Posts: 30,000
  • Înscris: 27.09.2008

View Posttavitu, on 19 mai 2017 - 15:18, said:

Aș calcula și salva toate numere prime până la radical din maxX inclusiv.

Pe panta asta pe masura ce generezi numerele prime de fapt e bine sa le testezi sa vezi daca sint factori la numerele tale. Oricum o sa faci asta mai incolo dar ai sanse sa scapi calculind numerele prime doar pina la un numar mult mai mic.

Deci din calcul pina la radical din max ramii mereu cu calculul pina la radical (max din ce ramine din fiecare numar).

In plus o mica optimizare (luam cazul unui singur numar) e ca nu trebuie calculat pina la radical din X ci e suficient de testat daca X e patrat perfect. Daca e am redus problema considerabil (ca avem de cautat factori primi pina la X1/4 cel mult. Daca nu atunci nu avem ce sa mergem mai sus de X1/3 pentru ca oricum nu mai gasim prime la puteri cel putin egale cu 2 in descompunerea lui X.

#5
Baggins

Baggins

    Member

  • Grup: Members
  • Posts: 264
  • Înscris: 09.10.2014

Quote

Eu unul aș afla cea mai mare valoare din x, un maxX. Aș calcula și salva toate numere prime până la radical din maxX inclusiv. Cel mai probabil în metoda inloc. Și apoi în metoda redus m-aș folosi de numerele prime salvate anterior ca să aflu ce trebuie.
Nu prea înțeleg. Să luăm exemplul dat de ei.
Intră
7
7 18 18 5 14 20 4

Iese
14 10 7 6 6 5 2

Caut maximul din șir => maxX=20
Numerele prime până la sqrt(20), inclusiv, sunt 2 și 3. Ok, și? Cum te folosești de astea?
Nu ar trebui să generez nr prime până la maxX, inclusiv?
Dacă în exemplu ar fi fost un 23, eu în output trebuie să am un 23 și ca să-l am trebuie să-l salvez.

#6
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005
eu il dau exemplu pe 65

#7
Baggins

Baggins

    Member

  • Grup: Members
  • Posts: 264
  • Înscris: 09.10.2014
nu știu ce vrei să-mi sugerezi

#8
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005

Quote

Nu ar trebui să generez nr prime până la maxX, inclusiv?
65 -- tu chiar mergi pana la maxX ?

#9
Baggins

Baggins

    Member

  • Grup: Members
  • Posts: 264
  • Înscris: 09.10.2014
nu, până la jumate
până la radical(65) nu l-aș lua și pe 13

#10
tavitu

tavitu

    Minune: HE a început să emită facturile!

  • Grup: Senior Members
  • Posts: 5,598
  • Înscris: 16.02.2009
Un număr x are trei cazuri pentru redusul său:

1. dacă x = 1, atunci redusul său este 1
2. dacă x este număr prim redusul său este x
3. dacă x = pk * x2 redusul său este p * redusul lui x2, unde p este un număr prim

Ca să demonstrezi că un număr x este prim trebuie să verifici că x nu este divizibil cu nici un număr prim din intervalul [2, radical din x]. Pentru cazul doi trei trebui să ai acces la numere prime care pot face parte din x. Deci trebuie să ai access la numerele prime mai mici sau egale cu radical din x. Pe exemplul tău.

7
7 18 18 5 14 20 4

Valoarea maximă este 20, sqrt(20) =4,.. , numerele prime în intervalul [2, 4] sunt {2, 3}.

Pentru 7 - sqrt(7) = 2,... numere prime în intervalul [2, 2] sunt {2}, 7 nu este divizibil cu nici un număr prim din intervalul respectiv => 7 este număr prim => redusul lui 7 este 7
Pentru 18 - sqrt(18) = 4,... numere prime în intervalul [2, 4] sunt {2, 3}, 18 = 2*9 => redusul lui 18 este 2 * redusul lui 9 = 2 * 3 = 6
Pentru 9 - sqrt(9) = 3, numere prime în intervalul [2, 3] sunt {2, 3}, 9 = 32 * 1 => redusul lui 9 este 3 * redusul lui 1 = 3 * 1 = 3
etc

De fiecare dată ai nevoie să calculezi care sunt numerele prime dintr-un interval și apoi să verifici în care caz se încadrează numărul x. Nu are sens să calculezi de fiecare dată numerele prime pentru un număr x, {2, 3, 5, etc}. Tu ai încercat să faci ceva asemenător cu n % f, n% (f + 2) și f += 6, dar asta nu calculează doar numerele prime dintr-un interval ci si numere compuse, care nu de ce să fie verificate, și adaugă timp în mod inutil la durata de execuție.

Eu zic că în primă fază ar trebui să vezi cum generezi numerele prime până la inclusiv radical din valoarea maximă. Iar apoi să te gândești la o buclă care testează dacă un număr x este prim sau este pk * x2 folosindu-te de numerele prime și calculeză și redusul în același timp. Și vreau să corectez o afirmație pe care am făcut-o, trebuie să împarți numărul x la factorii primi ca să reduci spațiul de căutare, când am zis că nu are rost am greșit.

@f300
Da, am putea testa când le generăm dacă numerele prime sunt factori, dar asta implică ceva subtilități, nu are sens să testăm dacă un număr prim p este un factor prim al unui număr x dacă p > x. Având în vedere că redusul unui număr poate fi definit recursiv am putea folosi o strategie de caching pentru redus și alte optimizări.

Edited by tavitu, 19 May 2017 - 22:17.


#11
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005
Eu stiu de un singur caz,   produs de numere prime distincte

#12
tavitu

tavitu

    Minune: HE a început să emită facturile!

  • Grup: Senior Members
  • Posts: 5,598
  • Înscris: 16.02.2009
Depinde cum vrei să privești lucrurile, da, matematic vorbind e un produs de numere prime distincte. Eu am ales să privesc lucrurile într-un mod care ajută la calculat numerele prime respective.

#13
f300

f300

    30k si ma duc

  • Grup: Senior Members
  • Posts: 30,000
  • Înscris: 27.09.2008

View Posttavitu, on 19 mai 2017 - 22:15, said:

nu are sens să testăm dacă un număr prim p este un factor prim al unui număr x dacă p > x

E mai tare, trebuie testat doar pina la x1/3  in contextul problemei! Este o smecherie, in contextul problemei daca x nu e patrat perfect (lucru care se poate testa simplu) si ai testat toate primele cel mult egale cu x1/3 atunci "redusul" lui x e tot x, nu mai e nevoie sa testezi mai sus. Se poate demonstra usor, daca ai avea inca patrate ce divid x atunci x ar trebui sa fie de forma:

x = a2b    (1)

cu a si b avind factori primi strict mai mari decit x1/3, ceea ce ar inseamna ca a si b sint > x1/3 ceea ce contrazice (1).

Anunturi

Chirurgia spinală minim invazivă Chirurgia spinală minim invazivă

Chirurgia spinală minim invazivă oferă pacienților oportunitatea unui tratament eficient, permițându-le o recuperare ultra rapidă și nu în ultimul rând minimizând leziunile induse chirurgical.

Echipa noastră utilizează un spectru larg de tehnici minim invazive, din care enumerăm câteva: endoscopia cu variantele ei (transnazală, transtoracică, transmusculară, etc), microscopul operator, abordurile trans tubulare și nu în ultimul rând infiltrațiile la toate nivelurile coloanei vertebrale.

www.neurohope.ro

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate