Форум программистов, компьютерный форум CyberForum.ru

Простые числа - C++

Восстановить пароль Регистрация
 
kzht91
0 / 0 / 0
Регистрация: 02.07.2010
Сообщений: 19
20.08.2010, 17:19     Простые числа #1
У меня 2 задачи. Объясните, пожалуйста, просто алгоритмы.
1) Найти n-ное простое число (например n=10^5)
2) Разложение составного числа на простые
Пытаюсь написать на c++
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.08.2010, 17:19     Простые числа
Посмотрите здесь:

Простые числа. C++
Простые числа C++
не могу понять задачку :) Даны натуральные числа p и q. Получить все делители числа q, взаимно простые с p C++
C++ Одномерный массив. Вывести на экран все числа, индексы которых есть простые числа.
Найти все простые числа от 1000 до 1999, в каждом из которых сумма первой и второй цифр в записи этого числа равна сумме третьей и четвертой. C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
20.08.2010, 17:25     Простые числа #2
есть, только на делфи, перевести нетрудно.
Решение на Delphi
разложить на составные:
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
procedure TForm1.bbDelClick(Sender: TObject);
var
i,c, us : cardinal;
begin
us := seDel.Value;
if us >= 500000000 then
  if Application.MessageBox('Для вычислений потребуется достаточно много времени.' + #13 +'Вы согласны продолжить?','High Speed Calculations',MB_ICONEXCLAMATION + MB_YESNO) = mrNo then exit;
Screen.Cursor := crHourglass;
Application.ProcessMessages;
c := 0;
lbDel.Clear;
for i := 1 to us do begin
  if i > us div 2 then begin
    c := c + 1;
    lbDel.Items.Add(IntToStr(c) + ' делитель = ' + IntToStr(us));
    break;
  end;
  if us mod i = 0 then begin
    c := c + 1;
    lbDel.Items.Add(IntToStr(c) + ' делитель = ' + IntToStr(i));
    if us >= 500000000 then Application.ProcessMessages;
  end;
end;
Screen.Cursor := crDefault;
end;
найти н простых чисел:

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
procedure TForm1.bbProstClick(Sender: TObject);
var
pv, pd, dl : cardinal;
begin
if (seMax.Value - seLow.Value) > 10000 then
  if Application.MessageBox('Для вычислений потребуется достаточно много времени.' + #13 +'Вы согласны продолжить?','High Speed Calculations',MB_ICONEXCLAMATION + MB_YESNO) = mrNo then exit;
lbProst.Clear;
dl := 0;
for pv := seLow.Value + 1 to seMax.Value do begin
  for pd := 1 to pv do begin
    if Int(pv / pd) = pv / pd then dl := dl + 1;
  Application.ProcessMessages;
  end;
  if dl = 2 then lbProst.Items.Add('Простое число '+ IntToStr(pv));
  dl := 0;
end;
end;
kzht91
0 / 0 / 0
Регистрация: 02.07.2010
Сообщений: 19
20.08.2010, 17:29  [ТС]     Простые числа #3
Если честно, почти ничего не понял(((
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
20.08.2010, 17:38     Простые числа #4
Пользуемся поиском
Vladimir616
110 / 110 / 3
Регистрация: 05.07.2009
Сообщений: 224
20.08.2010, 17:38     Простые числа #5
kzht91,

№2


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
 
int main()
{
        int n = 0;
        cin >> n;
        for(int i = 2; i <= n/2;)
                if(n % i == 0)
                {
                        cout << i << endl;
                        n /= i;
                }
                else
                        i++;
        cout << n << endl;
        return 0;
}
KuKu
 Аватар для KuKu
1538 / 1016 / 69
Регистрация: 17.04.2009
Сообщений: 2,946
20.08.2010, 17:40     Простые числа #6
1)эм .. простые числа 1,2,3
гонишь цикл от 4 до тех пор пока не захочешь закончить, каждое число смотришь делится ли оно на все предыдущие простые числа без остатка. То есть 4 делится на 2, на наго забиваеем.Смотрим 5 на два не делится, делим на 3 - не делится, значит добавляем 5 в список простых чисел.Сейчас в списке простых чисел (2,3,5).Проверям дальше увеличивая список
Yandex
Объявления
20.08.2010, 17:40     Простые числа
Ответ Создать тему
Опции темы

Текущее время: 07:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru