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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Помагите по опер. повторения http://www.cyberforum.ru/cpp-beginners/thread71115.html
Это задача. Запрограммировать расчет точек и вывод на экран значений аргумента и функции f=sin(x)/x в виде таблицы.Диапозон изменения аргумента .Количество точек расчета задается с клавиатуры не меньше 3. Помагите позалуйста найти ошибки,завтра последний срок сдачи этой задачи. #include "stdafx.h" #include <iostream> #include <iomanip> #include <cmath>
C++ почему игнорируется метод класса #include <iostream.h> #include <stdlib.h> class Vect { private: double **p; double **p1; double **p2; int size1; int size2; int size11; http://www.cyberforum.ru/cpp-beginners/thread71103.html
Работа с текстовыми файлами. C++
Здравствуйте)) Не могли бы Вы мне помочь с такой задачей:создать текстовый файл. Найти номер самой длинной строки. Создавать файлы я умею..подскажите пожалуйста как найти номер самой длинной строки((
C++ Строки
1. Дана строка. Найти симметричные слова. Распечатать их в алфавитном порядке, если таких слов нет - выдать соответсвующие сообщение. 2. Найти в строке все слова, в которых каждая буква встречается более одного раза. Найденные слова вывести в алфавитном порядке. Если нужных слов нет, то выдать сообщение. 3. Найти самое короткое и длинное слово, в котором нет повторяющихся букв. Я...
C++ двумерный массив. Что возле нашего элемента. http://www.cyberforum.ru/cpp-beginners/thread71075.html
У меня есть двумерный массив 5*5. Я обхожу его двумя циклами фор: for(int i=0;i<5;i++) { for(int j=0;j<5;j++) { cout << "|" << arr_user_pole << "|"; } cout << "\n"; }
C++ Блоковый ввод-вывод Сформировать двоичный файл из элементов, заданной в варианте структуры, распечатать его содержимое, выполнить удаление и добавление элементов в соответствии со своим вариантом, используя для поиска удаляемых или добавляемых элементов функцию. Формирование, печать, добавление и удаление элементов оформить в виде функций. Предусмотреть сообщения об ошибках при открытии файла и выполнении операций... подробнее

Показать сообщение отдельно
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
07.12.2009, 11:42     Простые числа
из загашников : поиск простых делителей числа
C++
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*
немного рассуждений:
Пусть P_1,P_2, P_3, P_4,..,P_k-1, P_k - простые числа, причем P_i<P_i+1 при любых
 
i=1,2,3,....k-1.
любое число можно представить ввиде
n = {(P_1)^S_1}*{(P_2)^S_2}*{(P_3)^S_3}*{(p_4)^S_4}*.. .*{(P_k-1)^S_k-1}*{(P_k)^S_k} 
//^-возведение в степень 2^3=8;
где S_i = 0,1,2,3... кратность простого множителя.
оценим максимальный множитель:
так как P_i<P_i+1 оценим для P_k.
{(P_k)^S_k} = n/[{(P_1)^S_1}*{(P_2)^S_2}*{(P_3)^S_3}*...*{(P_k-1)^S_k-1}]
 
пусть сложилась ситуация, такая что
 
[{(P_1)^S_1}*{(P_2)^S_2}*{(P_3)^S_3}*{(p_4)^S_4}*.. .*{(P_k-1)^S_k-1}] = 1
то есть S_i = 0 для i = 1,2,3,4,.., k-2,k-1;
 
тогда {(P_k)^S_k} = n (а обычно меньше т.к. знаменатель обычно не равен 1), т.е.
{(P_k)^S_k} <= n
 
вариант 1: S_k = 0, невозможен при правильном k (доказывать не будем, впринципе очевидно.)
вариант 2: S_k = 1, n = P_k; n простое.
вариант 3: S_k = 2, p_k*p_k <= n т.е. p_k<= (n^0.5)
вариант 4: S_k = 3, p_k*p_k*p_k<=n p_k< (n^0.5)
 
таким образом проверять простые делители следует от 2 до значения квадратного корня из n 
включительно, а так же убедиться в том что n не являеться простым. (Последнее верно если 
нашелся хотя бы один делитель для n в указанном промежутке обязательно найдеться простой 
делитель;  если же нет, то n простое.)
 
#include<iostream.h>
 
/**********************************************************
cancellation() Выясняет являеться ли divisor делителем для 
number, если да, то находит кратность делителя и возвращает 
зачение (number/(divisor^S)) 
**********************************************************************/
 
 
/************************************************************************
Ведём перебор возможных делителей для number (он будет 
лежать в промежутке до корня из number включительно, если 
number - сложное, то возможное 
значение передаем функции cancellation(); перебор возможных 
делителей оптимизирован исключением чисел вида 2k, где 
k=1,2,3,4,5,6,...; по предложению cheburator'а возможно 
исключение чисел вида 3k, 5k  и т.п.
делителей оптимизирован исключением чисел вида 2k, где 
k=1,2,3,4,5,6,...; возможно 
исключение чисел вида 3k, 5k  и т.п.
*********************************************************************/
#include<iostream.h>
int cancellation(int divisor,int number);
 
int main()
{
 int n,number;
 cout<<"\nInput number..."<<endl; 
 cin>>n;
 cout<<"\nSolve..."<<endl;
 
 number=n;
 number=cancellation(2,number);
 
 int k=3;
 while (k*k <= number)
 {
   psi=cancellation(k,psi);
   k+=2;
 }
 
  cout<<number;
  cout<<"\nDone..."<<endl;
 
  return (0);
}
 
int cancellation (int divisor,int number)
{
 if ((number%divisor)==0) cout<<divisor<<"\t";
 while((number%divisor)==0) number/=divisor;
 return (number);
}
 
Текущее время: 22:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru