Простые числа. Решето Эратосфена - История изменений

Ctrlalt в 22:37, 14 августа 2024

2024-08-14T22:37:47Z

@@ Строка 1: / Строка 1: @@
 ===Проверка числа на простоту, O(sqrt(N))===
   bool isPrime(int n) {
       if (n < 2)
@@ Строка 10: / Строка 12: @@
       return 1;
+  }
 ===Получение списка делителей числа, O(sqrt(N))===

Ctrlalt в 17:04, 27 мая 2023

2023-05-27T17:04:39Z

@@ Строка 11: / Строка 11: @@
+  }
-===Получение списка всех делителей числа, O(sqrt(N))===
+===Получение списка делителей числа, O(sqrt(N))===
   vector<int> getDivisors(int n) {
       vector<int> divisors;
@@ Строка 26: / Строка 28: @@
       return divisors;
+  }
 ===Факторизация числа (получение списка простых делителей), O(sqrt(N))===

Ctrlalt в 17:02, 1 января 2023

2023-01-01T17:02:30Z

← Предыдущая версия		Версия от 17:02, 1 января 2023
Строка 65:		Строка 65:

	vector<int> getPrimes(int n) {		vector<int> getPrimes(int n) {
	vector<int> isPrime(n, 1), primes;		vector<int> isPrime(n + 1, 1), primes;

	for (int i = 2; i < isPrime.size(); i++) {		for (int i = 2; i < isPrime.size(); i++) {
Строка 80:		Строка 80:
	===Решето Эратосфена, O(N)===		===Решето Эратосфена, O(N)===
	vector<int> getPrimes(int n) {		vector<int> getPrimes(int n) {
	vector<int> minDivisor(n), primes;		vector<int> minDivisor(n + 1), primes;

	for (int i = 2; i < minDivisor.size(); i++) {		for (int i = 2; i < minDivisor.size(); i++) {

Ctrlalt в 15:18, 18 декабря 2022

2022-12-18T15:18:23Z

← Предыдущая версия		Версия от 15:18, 18 декабря 2022
Строка 64:		Строка 64:
	===Решето Эратосфена, O(NloglogN)===		===Решето Эратосфена, O(NloglogN)===

	vector<int> getPrimes() {		vector<int> getPrimes(int n) {
	~~const int N = 1e6;~~		vector<int> isPrime(n, 1), primes;
	vector<int> isPrime(N, 1), primes;
			for (int i = 2; i < isPrime.size(); i++) {
	for (int i = 2; i < N; i++) {
	if (isPrime[i]) {		if (isPrime[i]) {
	primes.push_back(i);		primes.push_back(i);
	for (long long j = 1LL * i * i; j < N; j += i)		for (long long j = 1LL * i * i; j < isPrime.size(); j += i)
	isPrime[j] = 0;		isPrime[j] = 0;
	}		}
	}		}

	return primes;		return primes;
	}		}

	===Решето Эратосфена, O(N)===		===Решето Эратосфена, O(N)===
	vector<int> getPrimes() {		vector<int> getPrimes(int n) {
	~~const int N = 1e6;~~		vector<int> minDivisor(n), primes;
	vector<int> minDivisor(N), primes;
			for (int i = 2; i < minDivisor.size(); i++) {
	for (int i = 2; i < N; i++) {
	if (!minDivisor[i]) {		if (!minDivisor[i]) {
	minDivisor[i] = i;		minDivisor[i] = i;
	primes.push_back(i);		primes.push_back(i);
	}		}
	for (int j = 0; j < primes.size() && primes[j] <= minDivisor[i] && 1LL * i * primes[j] < N; j++)		for (int j = 0; j < primes.size() && primes[j] <= minDivisor[i] && 1LL * i * primes[j] < minDivisor.size(); j++)
	minDivisor[i * primes[j]] = primes[j];		minDivisor[i * primes[j]] = primes[j];
	}		}

	return primes;		return primes;
	}		}

Ctrlalt: /* Факторизация числа (получение списка простых делителей), O(sqrt(N)) */

2022-11-15T03:54:53Z

Факторизация числа (получение списка простых делителей), O(sqrt(N))

@@ Строка 28: / Строка 28: @@
 ===Факторизация числа (получение списка простых делителей), O(sqrt(N))===
   vector<int> factorize(int n) {
       vector<int> factorization;
@@ Строка 42: / Строка 44: @@
       return factorization;
+  }
 ===Решето Эратосфена, O(NloglogN)===

Ctrlalt: /* Получение списка всех делителей числа, O(sqrt(N)) */

2022-08-26T06:24:09Z

Получение списка всех делителей числа, O(sqrt(N))

← Предыдущая версия		Версия от 06:24, 26 августа 2022
Строка 15:		Строка 15:
	vector<int> divisors;		vector<int> divisors;

	for (long long d = 1; d * d <= n; i++) {		for (long long d = 1; d * d <= n; d++) {
	if (n % d == 0) {		if (n % d == 0) {
	divisors.push_back(d);		divisors.push_back(d);

Ctrlalt в 13:04, 29 июля 2022

2022-07-29T13:04:40Z

← Предыдущая версия		Версия от 13:04, 29 июля 2022
Строка 4:		Строка 4:
	return 0;		return 0;

	for (long long i = 2; i * i <= n; i++)		for (long long d = 2; d * d <= n; d++)
	if (n % i == 0)		if (n % d == 0)
	return 0;		return 0;

Строка 15:		Строка 15:
	vector<int> divisors;		vector<int> divisors;

	for (long long i = 1; i * i <= n; i++) {		for (long long d = 1; d * d <= n; i++) {
	if (n % i == 0) {		if (n % d == 0) {
	divisors.push_back(i);		divisors.push_back(d);
	if (i * i != n)		if (d * d != n)
	divisors.push_back(n / i);		divisors.push_back(n / d);
	}		}
	}		}
Строка 31:		Строка 31:
	vector<int> factorization;		vector<int> factorization;

	for (long long i = 2; i * i <= n; i++) {		for (long long d = 2; d * d <= n; d++) {
	while (n % i == 0) {		while (n % d == 0) {
	factorization.push_back(i);		factorization.push_back(d);
	n /= i;		n /= d;
	}		}
	}		}

Ctrlalt в 14:28, 3 июня 2021

2021-06-03T14:28:09Z

← Предыдущая версия		Версия от 14:28, 3 июня 2021
Строка 4:		Строка 4:
	return 0;		return 0;

	for (~~int~~ i = 2; i * i <= n; i++)		for (long long i = 2; i * i <= n; i++)
	if (n % i == 0)		if (n % i == 0)
	return 0;		return 0;
Строка 15:		Строка 15:
	vector<int> divisors;		vector<int> divisors;

	for (~~int~~ i = 1; i * i <= n; i++) {		for (long long i = 1; i * i <= n; i++) {
	if (n % i == 0) {		if (n % i == 0) {
	divisors.push_back(i);		divisors.push_back(i);
Строка 31:		Строка 31:
	vector<int> factorization;		vector<int> factorization;

	for (~~int~~ i = 2; i * i <= n; i++) {		for (long long i = 2; i * i <= n; i++) {
	while (n % i == 0) {		while (n % i == 0) {
	factorization.push_back(i);		factorization.push_back(i);

Ctrlalt в 06:39, 25 марта 2021

2021-03-25T06:39:10Z

← Предыдущая версия		Версия от 06:39, 25 марта 2021
Строка 42:		Строка 42:
	return factorization;		return factorization;
	}		}


	===Решето Эратосфена, O(NloglogN)===		===Решето Эратосфена, O(NloglogN)===

Ctrlalt в 06:38, 25 марта 2021

2021-03-25T06:38:49Z

← Предыдущая версия		Версия от 06:38, 25 марта 2021
Строка 1:		Строка 1:
			===Проверка числа на простоту, O(sqrt(N))===
			bool isPrime(int n) {
			if (n < 2)
			return 0;

			for (int i = 2; i * i <= n; i++)
			if (n % i == 0)
			return 0;

			return 1;
			}

	O(~~NloglogN~~)		===Получение списка всех делителей числа, O(sqrt(N))===
	~~const~~ int ~~N = 1000010;~~		vector<int> getDivisors(int n) {
	~~static bool p[N]~~;		vector<int> divisors;

	for (int i = 2; i < N; i++)		for (int i = 1; i * i <= n; i++) {
	if (~~!p[~~i] && 1LL * i * i ~~< N~~)		if (n % i == 0) {
	~~for~~ (~~int j =~~ i * i~~; j < N; j +~~= i)		divisors.push_back(i);
	~~p[j] = 1~~;		if (i * i != n)
			divisors.push_back(n / i);
			}
			}

			sort(divisors.begin(), divisors.end());
			return divisors;
			}

	O(N)		===Факторизация числа (получение списка простых делителей), O(sqrt(N))===
	~~const int N~~ = ~~1000010;~~		vector<int> factorize(int n) {
	vector<int> ~~primes;~~		vector<int> factorization;
	~~static~~ int ~~minDivisor[N]~~;
			for (int i = 2; i * i <= n; i++) {
	for (int i = 2; i < N; i++) {		while (n % i == 0) {
	if (~~!minDivisor[~~i]) {		factorization.push_back(i);
	~~minDivisor[~~i] = i;		n /= i;
	~~primes.push_back(i);~~		}
	}		}
	~~for~~ (~~int j~~ = ~~0; j < primes~~.~~size~~() ~~&& primes[j] <= minDivisor[i] && 1LL * i * primes[j] < N~~; ~~j++)~~		if (n != 1)
	~~minDivisor[i * primes[j]] = primes[j]~~;		factorization.push_back(n);

			return factorization;
	}		}

	== ~~Ссылки на задачи~~ ==
	* [~~http://acmp~~.~~ru/?main~~=~~task~~&~~id_task~~=~~200 ACMP #200~~ &~~mdash~~; ~~Марсианские факториалы~~]		===Решето Эратосфена, O(NloglogN)===

			vector<int> getPrimes() {
			const int N = 1e6;
			vector<int> isPrime(N, 1), primes;

			for (int i = 2; i < N; i++) {
			if (isPrime[i]) {
			primes.push_back(i);
			for (long long j = 1LL * i * i; j < N; j += i)
			isPrime[j] = 0;
			}
			}

			return primes;
			}

			===Решето Эратосфена, O(N)===
			vector<int> getPrimes() {
			const int N = 1e6;
			vector<int> minDivisor(N), primes;

			for (int i = 2; i < N; i++) {
			if (!minDivisor[i]) {
			minDivisor[i] = i;
			primes.push_back(i);
			}
			for (int j = 0; j < primes.size() && primes[j] <= minDivisor[i] && 1LL * i * primes[j] < N; j++)
			minDivisor[i * primes[j]] = primes[j];
			}

			return primes;
			}

	== Ссылки ==		== Ссылки ==
	* [http://e-maxx.ru/algo/eratosthenes_sieve E-Maxx — Решето Эратосфена]		Теория:
	* [http://e-maxx.ru/algo/prime_sieve_linear E-Maxx — Решето Эратосфена с линейным временем работы]		:* [http://e-maxx.ru/algo/eratosthenes_sieve E-Maxx — Решето Эратосфена]
	* [http://brestprog.by/topics/factorization Brestprog — Разложение числа на простые множители (факторизация). Делители числа]		:* [http://e-maxx.ru/algo/prime_sieve_linear E-Maxx — Решето Эратосфена с линейным временем работы]
	* [http://brestprog.by/topics/primesieve Brestprog — Решето Эратосфена]		:* [http://brestprog.by/topics/factorization Brestprog — Разложение числа на простые множители (факторизация). Делители числа]
	* [http://algorithmica.org/tg/number-theory algorithmica.org — Теория чисел]		:* [http://brestprog.by/topics/primesieve Brestprog — Решето Эратосфена]
	* [http://algorithmica.org/ru/eratosthenes algorithmica.org — Решето Эратосфена]		:* [http://algorithmica.org/tg/number-theory algorithmica.org — Теория чисел]
	* [http://informatics.mccme.ru/course/view.php?id=17 informatics.mccme.ru — Курс «Арифметика и числовые алгоритмы» — часть 1]		:* [http://algorithmica.org/ru/eratosthenes algorithmica.org — Решето Эратосфена]
	* [http://github.com/indy256/codelibrary/blob/master/java/src/PrimesAndDivisors.java CodeLibrary — Prime numbers, sieve of Eratosthenes, Euler's totient function]		:* [https://usaco.guide/gold/divis?lang=cpp#prime-factorization USACO Guide — Prime Factorization]
			Код:
			:* [https://github.com/indy256/codelibrary/blob/master/cpp/numbertheory/primes_and_divisors.cpp indy256/codelibrary/cpp/numbertheory/primes_and_divisors.cpp]
			:* [https://github.com/indy256/codelibrary/blob/master/cpp/numbertheory/factorization.cpp indy256/codelibrary/cpp/numbertheory/factorization.cpp]
			Задачи:
			:* [http://acmp.ru/?main=task&id_task=200 ACMP #200]
			:* [[:Категория: Задачи: Простые числа\|Задачи: Простые числа]]
			:* [http://informatics.mccme.ru/course/view.php?id=17 informatics.mccme.ru — Курс «Арифметика и числовые алгоритмы» — часть 1]


	[[Category:Арифметические алгоритмы]]		[[Category:Арифметические алгоритмы]]