Linux за българи: Форуми

Прости числа. 1 2 3 5 7 11 13 17.... Число, което се дели само на себе си и 1 без остатък е просто Трябва ми алгоритъм, който да открива такива. Мислех, мислех.. и не можах да го измисля   Някой да има идея? Може и директно осъществена на С/С++/Perl ?
Имах една идея, ама по-добре без нея Става дума за цикъл, който изрежда всичките числа (от 1 до 100 примерно) и за всяко от тях проверява дали се дели на всички останали. Много е тромаво, не върши работа. Сигурно го има като базова задача това в някой учебник по информатика. Да?

Търсенето на такъв алгоритъм е доста отдавна - има една "архимедова решетка" (edit: то било сито на Ератостен )дето действа по следния начин:
1. от множеството на естетствените числа изключваш всички числа след 2 и делими на 2 - т.е. 4, 6 и т.н.
2. изключваш всички числа след 3 и делими на 3
 и т.н.

Доколкото си спомням имаше някаква формула в учебника по математика за 4-7клас?!?!  (от моето време обаче) дето обясняват простите числа. За тази формула е доказано, обаче, че още на 6-милиардното число "гърми" - т.е. получава се число, което не е просто.

Ако намериш бърз алгоритъм доста ще спечелиш

Избери си
http://mathworld.wolfram.com/PrimeFormulas.html

А тук има PDF с алгоритъм, но е на псевдо език.
http://www.cse.iitk.ac.in/news/primality.html

Има един метод за намиране на прости числа, датиращ от III век пр.н.е и се нарича "сито на Ератостен" (Eratosten sieve). Това е класическа задача от "масиви". Само ти трябва много памет. Ето алгоритъм и изработка на C++:

http://www.cpp-home.com/tutorial.php?204_1

Ако те интересува повече, потърси в книжарниците "Алгоритми на C" от Робърт Седжуик (Algrithms in C, R. Sedgwick).

можеш да намериш подобен алгоритъм вече реализиран (при това доста ефективен) във всеки уважаващ себе си криптографски пакет: openssl, gnu pg, gnu crypt lib и компания. простите числа лежат в основата на повечето асиметрични криптографски системи (като rsa например).

prime95 не правеше ли точно това?

/* Rezultata e 1 ako e prosto, inache 0 */
char isPrime(unsigned n) {
  usnigned i = 2;
  if (2 == n)
    return 1;
  while (i <= sqrt(n)) {
    if (n % i == 0)
      return 0;
    i++
  }
}

Programa za namirane na prostite chisla do n po Eratosten
#include <stdio.h>
#define MAX 1000

unsigned n = 100; // purvite n prosti chisla
char sieve[MAX];

void go(unsigned n) {
  unsigned i = 2, j;
  while (i <= 2) {
    if (sieve == 0){
      printf("%u ", i);
      j = i;
      while (j <= n) {
        sieve[j] = 1;
        j += 1;
      }
    }
    i++;
  }
}

hippo, при мен твоята програмка за "Решето на Ератостен" не върви и не ми се търсеше грешката, затова пренаписах програмката и смятам, че така е доста по ясно (лично мнение).

Примерен код

#include<stdlib.h> int *sieve; void go(unsigned n) {         unsigned i, j;         for(i=0;i<n;i++) sieve[i]=1;         for(i=2;i<n;i++) {                 if(sieve[i])                         for(j=2*i;j<n;j+=i) sieve[j]=0;         } } main() {         unsigned i, n;         printf("Interval: ");         scanf("%d", &n);         sieve=(int *)malloc(n*sizeof(int));         go(n);         for(i=2;i<n;i++)                 if(sieve[i]) printf("%d ", i); }

Поздрави
cipher

Cipher, вярно е, че не работи. Написах го на прима виста. Грешка има на 8-мия ред от функцията go():
Вместо j += 1; трябва да е j += i; (ако искаш ще на правя patch   ).

Динамично заделената памет за sieve е по-добро решение, но не забравяй като си заделил памет да я освобождаваш с free() .

Cipher, благодаря за градивната критика

hippo, благодаря ти, аз ще се поправя.  А ти можеш да изчистиш и другата грешка, която си допуснал, за да може програмата наистина да работи: 2-ри ред от тялото на функцията go() цикълчето трябва да е не while(i<=2) { .., а while(i<=n) {...}.

cipher

Благодаря ви на всички за коментара Ама мислех, че ще е по-лесно