Автор Тема: Алгоритъм за намиране на прости числа  (Прочетена 16892 пъти)

ivanatora

  • Напреднали
  • *****
  • Публикации: 658
  • Distribution: Ubuntu 10.04
  • Window Manager: Fluxbox
    • Профил
    • WWW
Прости числа. 1 2 3 5 7 11 13 17.... Число, което се дели само на себе си и 1 без остатък е просто '<img'> Трябва ми алгоритъм, който да открива такива. Мислех, мислех.. и не можах да го измисля  '<img'> Някой да има идея? Може и директно осъществена на С/С++/Perl ?
Имах една идея, ама по-добре без нея '<img'> Става дума за цикъл, който изрежда всичките числа (от 1 до 100 примерно) и за всяко от тях проверява дали се дели на всички останали. Много е тромаво, не върши работа. Сигурно го има като базова задача това в някой учебник по информатика. Да?
Активен

peio

  • Напреднали
  • *****
  • Публикации: 74
    • Профил
Алгоритъм за намиране на прости числа
« Отговор #1 -: Apr 06, 2005, 17:53 »
Примерен код

#!/usr/bin/python

for n in range(2, 100000):
  for x in range(2, n):
      if n % x == 0:
          print n, 'equals', x, '*', n/x
          break
  else:
      print n, 'is a prime number'
Активен

VladSun

  • Напреднали
  • *****
  • Публикации: 2166
    • Профил
Алгоритъм за намиране на прости числа
« Отговор #2 -: Apr 06, 2005, 17:55 »
'<img'> Търсенето на такъв алгоритъм е доста отдавна - има една "архимедова решетка" (edit: то било сито на Ератостен '<img'> )дето действа по следния начин:
1. от множеството на естетствените числа изключваш всички числа след 2 и делими на 2 - т.е. 4, 6 и т.н.
2. изключваш всички числа след 3 и делими на 3
 и т.н.

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

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

KISS Principle ( Keep-It-Short-and-Simple )
http://openfmi.net/projects/flattc/
Има 10 вида хора на този свят - разбиращи двоичния код и тези, които не го разбират :P

romeo_ninov

  • Напреднали
  • *****
  • Публикации: 2155
    • Профил
Алгоритъм за намиране на прости числа
« Отговор #3 -: Apr 06, 2005, 19:58 »
Цитат (ivanatora @ Април 06 2005,18:48)
Прости числа. 1 2 3 5 7 11 13 17.... Число, което се дели само на себе си и 1 без остатък е просто '<img'> Трябва ми алгоритъм, който да открива такива. Мислех, мислех.. и не можах да го измисля  '<img'> Някой да има идея? Може и директно осъществена на С/С++/Perl ?
Имах една идея, ама по-добре без нея '<img'> Става дума за цикъл, който изрежда всичките числа (от 1 до 100 примерно) и за всяко от тях проверява дали се дели на всички останали. Много е тромаво, не върши работа. Сигурно го има като базова задача това в някой учебник по информатика. Да?

Между другото по дефиниция 1 НЕ Е просто число :-)
По-добре е да проверяваш дали се дели на простите числа, които си "колекционирал" до този момент
Активен

0x2B|~0x2B

hotrod

  • Напреднали
  • *****
  • Публикации: 15
    • Профил
Алгоритъм за намиране на прости числа
« Отговор #4 -: Apr 06, 2005, 23:58 »
Избери си '<img'>
http://mathworld.wolfram.com/PrimeFormulas.html

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

  • Гост
Алгоритъм за намиране на прости числа
« Отговор #5 -: Apr 07, 2005, 08:04 »
Има един метод за намиране на прости числа, датиращ от III век пр.н.е и се нарича "сито на Ератостен" (Eratosten sieve). Това е класическа задача от "масиви". Само ти трябва много памет. Ето алгоритъм и изработка на C++:

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

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

ivak

  • Напреднали
  • *****
  • Публикации: 156
    • Профил
Алгоритъм за намиране на прости числа
« Отговор #6 -: Apr 07, 2005, 12:37 »
можеш да намериш подобен алгоритъм вече реализиран (при това доста ефективен) във всеки уважаващ себе си криптографски пакет: openssl, gnu pg, gnu crypt lib и компания. простите числа лежат в основата на повечето асиметрични криптографски системи (като rsa например).
Активен

Cлoжнитe пpoблeми имaт пpocти и лecни зa paзбиpaнe гpeшни oтгoвopи.

saturn_vk

  • Напреднали
  • *****
  • Публикации: 215
    • Профил
Алгоритъм за намиране на прости числа
« Отговор #7 -: Apr 07, 2005, 16:05 »
prime95 не правеше ли точно това?
Активен

"That is not dead which can eternal lie,
And with strange aeons even death may die."

hippo

  • Напреднали
  • *****
  • Публикации: 47
    • Профил
Алгоритъм за намиране на прости числа
« Отговор #8 -: Apr 07, 2005, 16:58 »
/* 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++;
  }
}
Активен

  • Гост
Алгоритъм за намиране на прости числа
« Отговор #9 -: Apr 07, 2005, 18:07 »
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 '<img'>
Активен

hippo

  • Напреднали
  • *****
  • Публикации: 47
    • Профил
Алгоритъм за намиране на прости числа
« Отговор #10 -: Apr 08, 2005, 16:02 »
Cipher, вярно е, че не работи. Написах го на прима виста. Грешка има на 8-мия ред от функцията go():
Вместо j += 1; трябва да е j += i; (ако искаш ще на правя patch  '<img'> ).

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

Cipher, благодаря за градивната критика '<img'>
Активен

  • Гост
Алгоритъм за намиране на прости числа
« Отговор #11 -: Apr 10, 2005, 16:25 »
hippo, благодаря ти, аз ще се поправя. '<img'>  А ти можеш да изчистиш и другата грешка, която си допуснал, за да може програмата наистина да работи: 2-ри ред от тялото на функцията go() цикълчето трябва да е не while(i<=2) { .., а while(i<=n) {...}.

cipher '<img'>
Активен

ivanatora

  • Напреднали
  • *****
  • Публикации: 658
  • Distribution: Ubuntu 10.04
  • Window Manager: Fluxbox
    • Профил
    • WWW
Алгоритъм за намиране на прости числа
« Отговор #12 -: Apr 11, 2005, 13:40 »
Благодаря ви на всички за коментара '<img'> Ама мислех, че ще е по-лесно '<img'>
Активен