LINUX.ORG.RU
решено Форум — Development  

Алгоритм поиска простых чисел, объясните

 , , , ,


0

1

Привет. Есть вот такой код, он из книги Кочан Стефан «Язык программирования Си», стр. 117.

#include <stdio.h>
#include <stdbool.h>
#define SIZE 50

int main() {
    int primes[SIZE], prime_index = 2;
	bool is_prime;

	primes[0] = 2;
	primes[1] = 3;

	for (int p = 5; p <= SIZE; p += 2) {
		is_prime = true;
		for (int i = 1; is_prime && p / primes[i] >= primes[i]; i++) {
                        if (p % primes[i] == 0)
            	        is_prime = false;
		}
		if (is_prime) {
			primes[prime_index] = p;
			prime_index++;
		}
	}

	for (int i = 0; i < prime_index; i++) {
		printf("%i ", primes[i]);
		printf("\n");
	}
	return 0;
}

Я пытаюсь понять ход программы. Например: третья итерация главного цикла, p == 9; дальше идем во вложенный цикл и там встречаем эту строку, 

p / primes[i] >= primes[i]
получается, что 9 / 7 >= 7 условие не выполняется, т.к (1 >= 7) == false, но почему-то 9 не записывается как простое число. Или может я чего-то не понял.
Автор утверждает, что проверка эта нужна, чтобы узнать - значение p не превышает квадратного корня из prime_i.

Объясните пожалуйста.

★

Последнее исправление: CYB3R (всего исправлений: 2)
← Сериализация с архивацией
Задачи на применение структуры данных →

может я чего-то не понял.

Простое число делится только на себя и на 1. 9 не является простым числом, так как делится на 3.

Deleted
()

но почему-то 9 не записывается как простое число

9 не простое число.

Bfgeshka ★★★★★
()

получается, что 9 / 7 >= 7 условие не выполняется, т.к (1 >= 7) == false, но почему-то 9 не записывается как простое число

У тебя там цикл. is_prime проваливается на 9/3>=3.

tfs
()

после 7 следующее простое 11, 13, 17, 19

anonymous
()
Ответ на: комментарий от EXL

Решето

это одна из немногих тем, где «Решето» считается чем-то хорошим :-D

user_id_68054 ★★★★★
()
Ответ на: комментарий от user_id_68054

Какая классная портянка. Надо вместо обоев на стену зафигачить.

EXL ★★★★★
()
Ответ на: комментарий от i-rinat

Хороший пример для начинающих кодить на Си. Помогает проникнуться духом отчаяния.

а кстати код не такой уж и большой...

1371 #if HAVE_GMP
1372 static bool
1373 mp_prime_p (mpz_t n)
1374 {
1375   bool is_prime;
1376   mpz_t q, a, nm1, tmp;
1377   struct mp_factors factors;
1378 
1379   if (mpz_cmp_ui (n, 1) <= 0)
1380     return false;
1381 
1382   /* We have already casted out small primes. */
1383   if (mpz_cmp_ui (n, (long) FIRST_OMITTED_PRIME * FIRST_OMITTED_PRIME) < 0)
1384     return true;
1385 
1386   mpz_inits (q, a, nm1, tmp, NULL);
1387 
1388   /* Precomputation for Miller-Rabin.  */
1389   mpz_sub_ui (nm1, n, 1);
1390 
1391   /* Find q and k, where q is odd and n = 1 + 2**k * q.  */
1392   unsigned long int k = mpz_scan1 (nm1, 0);
1393   mpz_tdiv_q_2exp (q, nm1, k);
1394 
1395   mpz_set_ui (a, 2);
1396 
1397   /* Perform a Miller-Rabin test, finds most composites quickly.  */
1398   if (!mp_millerrabin (n, nm1, a, tmp, q, k))
1399     {
1400       is_prime = false;
1401       goto ret2;
1402     }
1403 
1404   if (flag_prove_primality)
1405     {
1406       /* Factor n-1 for Lucas.  */
1407       mpz_set (tmp, nm1);
1408       mp_factor (tmp, &factors);
1409     }
1410 
1411   /* Loop until Lucas proves our number prime, or Miller-Rabin proves our
1412      number composite.  */
1413   for (unsigned int r = 0; r < PRIMES_PTAB_ENTRIES; r++)
1414     {
1415       if (flag_prove_primality)
1416         {
1417           is_prime = true;
1418           for (unsigned long int i = 0; i < factors.nfactors && is_prime; i++)
1419             {
1420               mpz_divexact (tmp, nm1, factors.p[i]);
1421               mpz_powm (tmp, a, tmp, n);
1422               is_prime = mpz_cmp_ui (tmp, 1) != 0;
1423             }
1424         }
1425       else
1426         {
1427           /* After enough Miller-Rabin runs, be content. */
1428           is_prime = (r == MR_REPS - 1);
1429         }
1430 
1431       if (is_prime)
1432         goto ret1;
1433 
1434       mpz_add_ui (a, a, primes_diff[r]);        /* Establish new base.  */
1435 
1436       if (!mp_millerrabin (n, nm1, a, tmp, q, k))
1437         {
1438           is_prime = false;
1439           goto ret1;
1440         }
1441     }
1442 
1443   error (0, 0, _("Lucas prime test failure.  This should not happen"));
1444   abort ();
1445 
1446  ret1:
1447   if (flag_prove_primality)
1448     mp_factor_clear (&factors);
1449  ret2:
1450   mpz_clears (q, a, nm1, tmp, NULL);
1451 
1452   return is_prime;
1453 }
1454 #endif

остальное — макросы и всякая UI-ерунда :-)

user_id_68054 ★★★★★
()
Ответ на: комментарий от tfs

оО. То что надо, я как-то зациклился на одном, а мы же подставляем первый элемент нашего массива простых чисел, а там 3. Спасибо.

ChuCha ★
() автор топика

Спасибо всем за ответы

ChuCha ★
() автор топика

Грубо говоря, ты не будешь делить после этой проверки 2 на 3, потому что 2 не может включать в себя 3. Никак. Спишь мало?

anonymous
()
Ответ на: комментарий от unt1tled

Нет. Этот просто завтыкал, а анонiмус дурак, но умничает.

cdshines ★★★★★
()
Ответ на: комментарий от user_id_68054

Какой прекрасный склад велосипедов с комментариями в традиционно гомеопатических дозах.

nezamudich ★★
()

встречаем эту строку, 

p / primes[i] >= primes[i]

перепиши ее как 

p >= primes[i] * primes[i]
и станет понятно что она делает

chuzhoi ★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Сериализация с архивацией
Development
Задачи на применение структуры данных →