2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней. На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 46  След.
 
 Re: Поиск простых чисел
Сообщение30.08.2009, 01:09 
Заслуженный участник


04/05/09
4587
SerjeyMinsk в сообщении #239016 писал(а):
К сожалению я не знаток программирования. Если Вы хотите действительно помочь, то помогите составить в паскале решето эратосфена (к примеру) (в википедии я видел уже готовое решение) с уже вставленным обращением к системному таймеру, а я уж на основе попробую (с вашими советами, если сможете) вставить по аналогу в этот алгоритм. Вот и будут все данные о скорости на языке цифр.

Вот вам примитивная реализация решета Эратосфена:
Код:
Program primes;

{
Get current time as precise as possible.
You can replace this function with anything suitable on your compiler.
This version reads CPU clock counter with RDTSC instruction.
It's then divided by the clock frequency - replace it with frequency of your CPU.
I have 2.4 GHz Intel Core 2 processor.
}
Function FineTime : Real;
Var
   frequency : Real = 2.4e9; { CPU frequency }
   clock     : Cardinal attribute (Size = 64);
begin
   asm volatile("rdtsc" : "=A" (clock));
   FineTime := clock / frequency;
end;

{ Count number of primes up to n using simple sieve of Eratosthenes. }
Function prime_count1(n : Integer) : Integer;
Type
   TSieve = Array[0..999999999] of Boolean;
   PSieve = ^TSieve;
Var       
   i           : Integer;
   j           : Integer;
   prime_count : Integer;
   prime       : PSieve; { dynamically allocated array for the sieve }
begin
   GetMem(prime, (n+1)*sizeof(Boolean)); { allocate the sieve array }
   FillChar(prime^, (n+1)*sizeof(Boolean), True); { fill it with ones }
   prime_count := 0;
   for i := 2 to n do
   begin
      if prime^[i] then { next prime found }
      begin
         Inc(prime_count);
         { mark all multiplies as non-primes: }
         j := i*2;
         while j <= n do
         begin
            prime^[j] := False;
            Inc(j, i);
         end;
      end;
   end;
   FreeMem(prime, (n+1)*sizeof(Boolean)); { free sieve array }
   prime_count1 := prime_count;
end;

{ run prime counting function and determine its runtime }
Procedure test1(n : Integer);
Var
   count : Integer;
   time  : Real;
begin
   time := FineTime();
   count := prime_count1(n);
   time := FineTime() - time;
   WriteLn('Number of primes up to ',n,' - ',count,'   time spent: ',time:0:3,' secs');
end;
   
begin
   test1(100000);
   test1(1000000);
   test1(10000000);
   test1(100000000);
end.


Цитата:
Неужели Вы не видите главного, в том, что вычисляется сам ряд чисел, а не проверяется какое-то одно?
Так ведь в решете Эратосфена тоже вычисляется сам ряд чисел.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение30.08.2009, 13:13 


23/01/07
3497
Новосибирск
SerjeyMinsk в сообщении #238917 писал(а):
Если у Вас есть примеры алгоритмов, которые находят ряд простых чисел, то дайте, пожалуйста, что-либо почитать об этом.

Альтернатива решету Эратосфена:

Вдоль ряда натуральных чисел обратным концом продвигается линейка с переменным расстоянием между делениями: $1, 3, 5... (2n-1)$ и при каждом продвижении на одно деление производятся отметки делений линейки среди нечетных числах.
Числа, имеющие 2 метки, вычеркиваются.
Все нечетные числа, не превышающие $(6n-9)$и имеющие не более одной метки, записываются в список простых чисел, к которым затем добавляется простое $2$.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение30.08.2009, 13:43 
Аватара пользователя


07/07/09
346
Минск
venco в сообщении #239049 писал(а):
Вот вам примитивная реализация решета Эратосфена:
[code]

Так ведь в решете Эратосфена тоже вычисляется сам ряд чисел.

Только объясните еще как этот код вставить в паскаль. Сохранил в текстовом файле с расширением PAS и кодировкой ЮНИКОД, но при нажатии Shift +F9 выдает ошибку.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение30.08.2009, 14:30 
Заслуженный участник
Аватара пользователя


22/11/06
1096
Одесса, ОНУ ИМЭМ
Вам нужен компилятор для Pascal. Например, скачайте FreePascal (freepascal.org)

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение30.08.2009, 14:39 


21/06/09
60
Free Pascal не может интерпретировать этот кусок кода:
Код:
Function FineTime : Real;
Var
   frequency : Real = 2.4e9; { CPU frequency }
   clock     : Cardinal attribute (Size = 64);
begin
   asm volatile("rdtsc" : "=A" (clock));
   FineTime := clock / frequency;
end;

А именно «Cardinal attribute (Size = 64)» и «asm volatile("rdtsc" : "=A" (clock))».

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение30.08.2009, 14:42 
Заслуженный участник


11/05/08
32166
А это вовсе никакой и не Паскаль. Это некая экзотическая над ним надстройка.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение30.08.2009, 16:08 
Заслуженный участник


04/05/09
4587
Это GNU Pascal - http://www.gnu-pascal.de/gpc/h-index.html.
Я на Паскале практически не пишу, так что стандартной функции для получения точного времени не знаю (подозреваю, что её вообще нет). Прошу знатоков предложить стандартный метод.

-- Вс авг 30, 2009 09:11:19 --

SerjeyMinsk в сообщении #239127 писал(а):
Сохранил в текстовом файле с расширением PAS и кодировкой ЮНИКОД, но при нажатии Shift +F9 выдает ошибку.
Кстати, совет: если компилятор выдаёт ошибку, и вы спрашиваете, как с этим бороться, лучше привести и текст ошибки.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение30.08.2009, 16:25 
Аватара пользователя


07/07/09
346
Минск

error5 syntax error
- это ошибка возникает, если я ввожу тектовый файл решета эратосфена в турбопаскаль 7.1

Эта ошибка возникает если я ввожу тектовый файл решета эратосфена в free pascal Изображение


exited with exitedcod 201 -

эта ошибка возникает если я ввожу assa в free pascal любое число выше чем 201

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение30.08.2009, 16:37 
Заслуженный участник
Аватара пользователя


09/02/09
2089
Минск, Беларусь
http://www.ieeta.pt/~tos/software/prime_sieve.html

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение30.08.2009, 18:02 
Заслуженный участник


27/04/09
28128
Как видите, Pascal не разбирает Unicode

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение30.08.2009, 18:38 
Заслуженный участник
Аватара пользователя


13/08/08
14495
arseniiv, вот поэтому я и предлагаю реализовать алгоритм в excel. Намеренно не говорю -написать программу, потому, что согласен с Вами, что excel для этого не предназначен. Но несложные действия с числами в нём (слушайте, а вдруг excel это она? мне кажется -он. Как и word.) очень удобно производить. Даже и простые, но длинные, многоступенчатые расчёты лучше делать в excel, а не на калькуляторе. В случае ошибки можно вернуться на любой шаг.
И всё наглядно так. То же решето Эратосфена. Я просто думаю, что алгоритм автора прост, как всё гениальное. И уж excel не будет выдавать мерзких ошибок.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение30.08.2009, 18:59 
Заслуженный участник


27/04/09
28128
Ну, просто очень трудоёмко, думаю, алгоритмизировать формулами в ячейках.

gris в сообщении #239197 писал(а):
(слушайте, а вдруг excel это она? мне кажется -он. Как и word.)

Программа Excel - она, табличный процессор Excel - он, приложение Excel - оно :)

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение30.08.2009, 19:05 
Аватара пользователя


07/07/09
346
Минск
var
flag:array[1..1000] of integer;
a,b,c,n,y,i,j,k,d,p:integer;

Скажите, за что отвечает данный фрагмент? Нет ли тут ограничения?

Что вообще тут написано в переводе на русский

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение30.08.2009, 19:08 
Заслуженный участник


27/04/09
28128
Попробуйте заменить integer на longint тут и везде, где он встречается.

Что там написано:
Объявить переменную flag как массив из 1000 целых чисел и переменные a,...,p как целые. longint это более "объёмный" тип целых чисел. Кстати, ваш приятель ещё и хорошо форматировать текст программ не умеет, для удобочитаемости. Боюсь, там и ляпы с оптимизацией есть, но это уже увидим потом, когда вы выложите текст, если не перемените решение.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение30.08.2009, 19:13 
Заслуженный участник
Аватара пользователя


13/08/08
14495
SerjeyMinsk, в паскале надо определять тип каждой переменной, это очень строгиё язык. Это всё двухбайтные целые.

arseniiv, по-вашему и винда - он? Программный продукт. Нет уж. Excel - мужик. Лысоватый, с бородкой, глаза с прищуром, но добрые... Господи! Да неужели...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 682 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 46  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group