Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Arte Martiale - avantaje/dezavant...

Problema telefon

Haine albe patate cu roz la spalat

Allview imperia i8
 Taskbarul devine neresponziv

Coolpad Torino S2

Digi24 - post de stiri lipsit de ...

Galaxy A5 (2016) - Problema sunet
 Ne pot citi p.m-urile dintre noi ...

Cum pornesc sursa server SUN spas...

Polaroid (2017)

Cum scap de acest tip de gandaci?...
 Sfat Smart TV Panasonic

Jgheaburi la bloc, preț exag...

Obiect strain in ochi...senzatia ...

Atenție cum conduceți i...
 
Forumul Softpedia folosește "cookies" pentru a oferi utilizatorilor o experiență completă. Vezi detalii sau închide mesaj (x)

Factori primi

  • Please log in to reply
12 replies to this topic

#1
Baggins

Baggins

    Junior

  • Grup: Members
  • Posts: 146
  • Înscris: 09.10.2014
  • ID membru: 882,130
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

    Active Member

  • Grup: Members
  • Posts: 1,472
  • Înscris: 16.02.2009
  • ID membru: 420,799
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: Moderators
  • Posts: 21,985
  • Înscris: 24.02.2007
  • ID membru: 146,987

Quote

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

Posted Image

#4
f300

f300

    see you in 2018

  • Grup: Senior Members
  • Posts: 27,084
  • Înscris: 27.09.2008
  • ID membru: 374,346

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

    Junior

  • Grup: Members
  • Posts: 146
  • Înscris: 09.10.2014
  • ID membru: 882,130

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

    Guru Member

  • Grup: Moderators
  • Posts: 16,394
  • Înscris: 10.08.2005
  • ID membru: 43,530
  • Locație: Iasi
eu il dau exemplu pe 65

#7
Baggins

Baggins

    Junior

  • Grup: Members
  • Posts: 146
  • Înscris: 09.10.2014
  • ID membru: 882,130
nu știu ce vrei să-mi sugerezi

#8
MarianG

MarianG

    Guru Member

  • Grup: Moderators
  • Posts: 16,394
  • Înscris: 10.08.2005
  • ID membru: 43,530
  • Locație: Iasi

Quote

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

#9
Baggins

Baggins

    Junior

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

#10
tavitu

tavitu

    Active Member

  • Grup: Members
  • Posts: 1,472
  • Înscris: 16.02.2009
  • ID membru: 420,799
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

    Guru Member

  • Grup: Moderators
  • Posts: 16,394
  • Înscris: 10.08.2005
  • ID membru: 43,530
  • Locație: Iasi
Eu stiu de un singur caz,   produs de numere prime distincte

#12
tavitu

tavitu

    Active Member

  • Grup: Members
  • Posts: 1,472
  • Înscris: 16.02.2009
  • ID membru: 420,799
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

    see you in 2018

  • Grup: Senior Members
  • Posts: 27,084
  • Înscris: 27.09.2008
  • ID membru: 374,346

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


0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users