I have array and I need display numbers divisible by the same number?

[chebyrek]

How to deduce from an array of numbers divisible by the same number?
I understand how you can determine if two numbers are divisible by the same thing using Euclid's method. With array I do not understand how to do it.

[jonnin]

is it a boolean answer? That is, is the question 'are all numbers in array divisible by 10' or is the question "which values in array are divisible by 10" or, worse, "what is the GCD of all the numbers in this array"?

If its the GCD of multiple numbers, I think I would sort the array from smallest to largest and get the prime factors of the smallest number, then check the largest of those against the rest of the array, for all the factors of the first one. But there may be a better way. Finding the factors of the numbers, if they are big enough, is an unholy problem (encryption theory is build around this hard problem). But if they are only 64 bit, it can still be done very quickly ... you 'only' have to check all the primes that fit in a 32 bit number, which is doable on a modern PC in very little time. And most numbers in range have less than 10 (distinct*) factors. You would have to sit down and theory at it a bit more than this... the GCD does not have to be prime... but the GCD will be some multiplication-combination of the prime factors of the first number (and repeats matter there...). Or you can look up the answer, but figuring it out would be more fun. If you look it up, the brute force way is: GCD(a,b,c,d) == GCD(GCD(GCD(a,b),c),d) .... but for a large array some subset will give you candidates to try on the rest, some sort of reduction like that will speed it up a lot... when a candidate fails the failure gives you a new candidate... which is what I was trying to do at the start of this ramble, but from the other side.

it is often overlooked but c++ has GCD build in.

[chebyrek]

I sorted the array from smaller to larger. The answer must be a pair of numbers divisible by the same number. I used Euclid's method. I think you can find the divisor of the maximum number and then specify other numbers that are divisible by the same number.

[jonnin]

Ok. If you get stuck, let us know...

[chebyrek]

I wrote this code, but it doesn't work correctly. Correct what is wrong.
int GCD(int a, int b)

{
while (b != 0)
{
int t = b;
b = a % b;
a = t;
}
return a;

}
int main()
{
setlocale(LC_ALL, "ru");
int num, start,c,d;
cout << "Введите размер массива:" << endl;
cin >> num;
cout << "Введите начальное значение:" << endl;
cin >> start;
cin >> d;
int* p_arr = new int[num];
for (int i = start; i < num; i++)
{
p_arr[i] = i;
cout << p_arr[i] << endl;
}
for (int i = start; i < num; i++)
{
c = GCD(p_arr[i],d);
cout << c << endl;
}
delete[] p_arr;
return 0;

}

[seeplus]

This is a simple brute-force method but is O(n2).

#include <iostream>

int main()
{
	int num {}, start {};

	std::cout << "How many numbers:";
	std::cin >> num;

	std::cout << "Start number:";
	std::cin >> start;

	for (int d = 2; d < (num + start) / 2; ++d) {
		std::cout << d << " : ";

		for (int i = start; i <= start + num; ++i)
			if (i % d == 0)
				std::cout << i << " ";

		std::cout << '\n';
	}
}

How many numbers:20
Start number:100
2 : 100 102 104 106 108 110 112 114 116 118 120
3 : 102 105 108 111 114 117 120
4 : 100 104 108 112 116 120
5 : 100 105 110 115 120
6 : 102 108 114 120
7 : 105 112 119
8 : 104 112 120
9 : 108 117
10 : 100 110 120
11 : 110
12 : 108 120
13 : 104 117
14 : 112
15 : 105 120
16 : 112
17 : 102 119
18 : 108
19 : 114
20 : 100 120
21 : 105
22 : 110
23 : 115
24 : 120
25 : 100
26 : 104
27 : 108
28 : 112
29 : 116
30 : 120
31 :
32 :
33 :
34 : 102
35 : 105
36 : 108
37 : 111
38 : 114
39 : 117
40 : 120
41 :
42 :
43 :
44 :
45 :
46 :
47 :
48 :
49 :
50 : 100
51 : 102
52 : 104
53 : 106
54 : 108
55 : 110
56 : 112
57 : 114
58 : 116
59 : 118

[seeplus]

If you want to store the numbers, then using a map:

#include <iostream>
#include <map>
#include <vector>

int main()
{
	std::map<int, std::vector<int>> divisible;
	int num {}, start {};

	std::cout << "How many numbers:";
	std::cin >> num;

	std::cout << "Start number:";
	std::cin >> start;

	for (int d = 2; d < (num + start) / 2; ++d)
		for (int i = start; i <= start + num; ++i)
			if (i % d == 0)
				divisible[d].push_back(i);

	for (const auto& [divisor, nos] : divisible) {
		std::cout << divisor << ": ";

		for (const auto& n : nos)
			std::cout << n << ' ';

		std::cout << '\n';
	}
}

How many numbers:20
Start number:50
2: 50 52 54 56 58 60 62 64 66 68 70
3: 51 54 57 60 63 66 69
4: 52 56 60 64 68
5: 50 55 60 65 70
6: 54 60 66
7: 56 63 70
8: 56 64
9: 54 63
10: 50 60 70
11: 55 66
12: 60
13: 52 65
14: 56 70
15: 60
16: 64
17: 51 68
18: 54
19: 57
20: 60
21: 63
22: 66
23: 69
25: 50
26: 52
27: 54
28: 56
29: 58
30: 60
31: 62
32: 64
33: 66
34: 68