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

Поиск простых чисел в массиве - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.58
Heidel
 Аватар для Heidel
110 / 110 / 7
Регистрация: 11.10.2011
Сообщений: 647
27.12.2011, 16:47     Поиск простых чисел в массиве #1
Здесь, на форуме для начинающих, была задачка, в которой в матрице A(m,n), состоящей из целых чисел, нужно было найти простые числа (те, что имеют ровно два различных натуральных делителя: единицу и самого себя) и далее с ними работать.
Я попробовала еще сделать, но застопорилась на этапе поиска простых чисел в матрице.
Для поиска простых чисел я решила пользоваться теоремой Вильсона:
p — простое число тогда и только тогда, когда (p − 1)! + 1 делится на p
Вот код моей программы:
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
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cmath>
using namespace std;
 
double factorial (int n)
{
    if (n <= 1) return 1.0;
    return (double) n * factorial (n-1);
}
 
int main ()
{
    srand(time(NULL));
    
    int i, j;
    int m, n;
    int** a;
 
    cout << "Vvedite kilichestvo strok m = ";
    cin >> m;
    cout << "Vvedite kolichestvo stolbzov n = ";
    cin >> n;
 
    cout << "\nMatriza razmerom " << m << "x" << n << "\n\n";
 
    a = new int* [m];
    for (i = 0; i < m; ++i)
    {
        a[i] = new int[n];
        for (j = 0; j < n; ++j)
        {
            a[i][j] = rand()%101;
            cout << a[i][j] << "\t";
        }
        cout <<"\n";
    }
 
    int x = 0;
    for (i = 0; i < m; ++i)
    {
        for (j = 0; j < n; ++j)
        {
            if ( (a[i][j]>=2) && fmod((factorial(a[i][j]-1)+1.0), (a[i][j])) == 0.0) //îïðåäåëåГ*ГЁГҐ ïðîñòîòû Г·ГЁГ±Г«Г* ГЇГ® òåîðåìå ÂèëüñîГ*Г*
            {
                cout << a[i][j] << " ";
                ++x;
            }
        }
    }
 
    cout << "\nx = " <<x << "\n";
 
    for(i = 0; i < m; ++i)
    delete[] a[i];
 
        delete[] a;
    
    return 0;
}
Если задать диапазон случайных чисел от 0 до 20
C++
1
a[i][j] = rand()%21;
то программа работает корректно, по крайней мере, сколько я не пробовала, находит правильные числа.
Если задавать диапазон больше, то программа работает неправильно: вперемешку с правильными числами выдает неподходящие, а часть правильных наоборот не находит.
Факториал чисел до 100 должен входить в диапазон значений дабл - на моем компьютере:
largest double==1.79769e+308
smallest double==2.22507e-308
,
а 100! = 9,33e+157.
Что не правильно?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.12.2011, 16:47     Поиск простых чисел в массиве
Посмотрите здесь:

C++ Нахождение простых чисел в массиве
Найти сумму простых чисел в массиве C++
Конкурс(поиск простых чисел) C++
C++ Поиск простых чисел
C++ Поиск простых чисел
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vandris
 Аватар для Vandris
63 / 63 / 13
Регистрация: 19.01.2011
Сообщений: 90
27.12.2011, 18:03     Поиск простых чисел в массиве #2
не правильно то, что double хранит по моему 15 верных знаков после запятой, сравните то что вам выдаст factorial(100), с например 100!. Ищите простые числа например так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
 
bool is_prime(int);
 
int main()
{
    for (int i = 0; i < 1000; i++)
        if (is_prime(i))
            std::cout << i << " ";
}
 
bool is_prime(int number)
{
    if (number == 1)
        return false;
    for (int i = 2; i < number/2. + 1; i++)
        if (number % i == 0)
            return false;
    return true;
}
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
27.12.2011, 18:12     Поиск простых чисел в массиве #3
Цитата Сообщение от Heidel Посмотреть сообщение
Для поиска простых чисел я решила пользоваться теоремой Вильсона:
Обязательно ее использовать? Вещественные типы использовать не рекомендую. Или для сравнение придется использовать "точность" (ну или погрешность). Вывод: если теорему обязательно использовать, то максимум можно использовать unsigned long. Но смыла в ней нет
Heidel
 Аватар для Heidel
110 / 110 / 7
Регистрация: 11.10.2011
Сообщений: 647
28.12.2011, 09:28  [ТС]     Поиск простых чисел в массиве #4
В конечном итоге написала так
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
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cmath>
using namespace std;
 
int main ()
{
    srand(time(NULL));
    
    int i, j;
    int m, n;
    int** a;
 
    cout << "Vvedite kilichestvo strok m = ";
    cin >> m;
    cout << "Vvedite kolichestvo stolbzov n = ";
    cin >> n;
 
    cout << "\nMatriza razmerom " << m << "x" << n << "\n\n";
 
    a = new int* [m];
    for (i = 0; i < m; ++i)
    {
        a[i] = new int[n];
        for (j = 0; j < n; ++j)
        {
            a[i][j] = rand()%21;
            cout << a[i][j] << "\t";
        }
        cout <<"\n";
    }
 
    int count = 0;
    for (i = 0; i < m; ++i)
    {
        for (j = 0; j < n; ++j)
        {
            if (a[i][j]>=2)
            {
                for (int k = 2; k <= a[i][j]; ++k)
                {
                    if(a[i][j]%k == 0)
                    {
                        ++count;
                    }
                }
 
                if(count==1)
                {
                    cout << a[i][j] << " ";
                }
            }
            count = 0;
        }
    }
 
    cout <<"\n";
 
    for(i = 0; i < m; ++i)
    delete[] a[i];
 
        delete[] a;
    
    return 0;
}
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
28.12.2011, 11:23     Поиск простых чисел в массиве #5
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/begin.hpp>
#include <boost/mpl/end.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/modulus.hpp>
#include <boost/mpl/equal_to.hpp>
#include <boost/mpl/plus.hpp>
#include <boost/mpl/vector_c.hpp>
#include <boost/mpl/deref.hpp>
 
namespace mpl = boost::mpl;
 
template<int N, int X>
struct IsDivide
{
   typedef typename mpl::if_
   <
      mpl::modulus
      <
         mpl::int_<N>, mpl::int_<X>
      >,
      mpl::false_,
      mpl::true_
   >::type type;
};
 
template<int N>
struct IsDivide<N, 1>
{
   typedef mpl::true_ type;
};
 
template<int N>
struct IsDivide<N, 0>
{
   typedef mpl::true_ type;
};
 
template<int N, int X>
struct CalcDivs
{
   typedef typename mpl::plus
   <
      typename CalcDivs<N, X - 1>::type,
      typename mpl::if_
      <
         typename IsDivide<N, X>::type,
         mpl::int_<X>,
         mpl::int_<0>
      >::type
   >::type type;
};
 
template<int N>
struct CalcDivs<N, 1>
{
   typedef typename mpl::int_<0> type;
};
 
template<int N>
struct CalcDivs<N, 0>
{
   typedef typename mpl::int_<0> type;
};
 
template<int N>
struct IsPrime
{
   typedef typename mpl::equal_to
   <
      mpl::int_<0>,
      typename CalcDivs<N, N / 2>::type
   >::type type;
};
 
template<int N>
struct PrintIfPrime
{
   typedef typename IsPrime<N>::type type;
   static void apply()
   {
      if (type::type::value)
      {
         std::cout << N << std::endl;
      }
   }
};
 
template<>
struct PrintIfPrime<0>
{
   static void apply()
   {
   }
};
 
template<class First, class Last>
struct PrintPrimes
{
   static void apply()
   {
      PrintIfPrime<mpl::deref<First>::type::value >::apply();
      PrintPrimes<typename mpl::next<First>::type, Last>::apply();
   }
};
 
template<class Last>
struct PrintPrimes<Last, Last>
{
   static void apply()
   {
   }
};
 
template<class Sequence>
void Print()
{
   PrintPrimes<typename mpl::begin<Sequence>::type, typename mpl::end<Sequence>::type >::apply();
};
 
int main()
{
   typedef mpl::vector_c<int, 1,2,3,4,5,6,7,8,9,10> vector_type;
   Print<vector_type>();
}
Не матрица конечно, но все же.
-=ЮрА=-
Заблокирован
Автор FAQ
28.12.2011, 15:35     Поиск простых чисел в массиве #6
Цитата Сообщение от Heidel Посмотреть сообщение
Я попробовала еще сделать, но застопорилась на этапе поиска простых чисел в матрице.
Для поиска простых чисел я решила пользоваться теоремой Вильсона:
p — простое число тогда и только тогда, когда (p − 1)! + 1 делится на p
- код считающий по вильсону ниже(правда простые числа не так определяют)
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
#include <iostream>
#include <cstdlib>
using namespace std;
 
long fact(int val)
{
    long ret = val;
    if(0 < (val = val - 1))
        ret *= fact(val);
    return ret;
}
 
bool isDigitSimple(int p)
{
    bool bVal = false;
    long p_1 = fact(p - 1);
    if((p_1 + 1) % p == 0)
        bVal = true;
    return bVal;
}
 
int main()
{
    cout<<"Enter number elements in array : ";
    int i, n; cin>>n;
    int * a = new int[n];
    int nSimpleCount = 0;//Г‚Г*Г*Г·Г*ëå Г±Г·ГЁГІГ*ГҐГ¬ Г·ГІГ® Г¬Г*Г±Г±ГЁГў Г*ГҐ ñîäåðæèò ïðîñòûõ Г·ГЁГ±ГҐГ«
    cout<<"Rand-generated array\n";
    for(i = 0; i < n; i++)
        cout<<(a[i] = rand()%10)<<" ";
    cout<<"\nSimple numbers in array\n";
    for(i = 0; i < n; i++)
    {
        if(isDigitSimple(a[i]))
        {
            cout<<a[i]<<" ";
            nSimpleCount++;
        }
    }
    if(nSimpleCount < 1)
        cout<<"\nGenerated array not contain simple numbers\n";
    system("pause");
    delete [] a;
    return 0;
}
Enter number elements in array : 15
Rand-generated array
1 7 4 0 9 4 8 8 2 4 5 5 1 7 1
Simple numbers in array
1 7 Press any key to continue
Yandex
Объявления
28.12.2011, 15:35     Поиск простых чисел в массиве
Ответ Создать тему
Опции темы

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