Coprime triplets: Difference between revisions
Added C and Python
(Added C and Python) |
|||
Line 216:
25 27 22 31 35 12 37 41 18 43
47 20 33 49 26 45</pre>
=={{header|C}}==
<lang C>/*
************************
* *
* COPRIME TRIPLETS *
* *
************************
*/
/* Starting from the sequence a(1)=1 and a(2)=2 find the next smallest number
which is coprime to the last two predecessors and has not yet appeared in the
sequence.
p and q are coprimes if they have no common factors other than 1.
Let p, q < 50 */
#include <stdio.h>
int Gcd(int v1, int v2)
{
/* It evaluates the Greatest Common Divisor between v1 and v2 */
int a, b, r;
if (v1 < v2)
{
a = v2;
b = v1;
}
else
{
a = v1;
b = v2;
}
do
{
r = a % b;
if (r == 0)
{
break;
}
else
{
a = b;
b = r;
}
} while (1 == 1);
return b;
}
int NotInList(int num, int numtrip, int *tripletslist)
{
/* It indicates if the value num is already present in the list tripletslist of length numtrip */
for (int i = 0; i < numtrip; i++)
{
if (num == tripletslist[i])
{
return 0;
}
}
return 1;
}
int main()
{
int coprime[50];
int gcd1, gcd2;
int ntrip = 2;
int n = 3;
/* The first two values */
coprime[0] = 1;
coprime[1] = 2;
while ( n < 50)
{
gcd1 = Gcd(n, coprime[ntrip-1]);
gcd2 = Gcd(n, coprime[ntrip-2]);
/* if n is coprime of the previous two value
and it isn't already present in the list */
if (gcd1 == 1 && gcd2 == 1 && NotInList(n, ntrip, coprime))
{
coprime[ntrip++] = n;
/* It starts searching a new triplets */
n = 3;
}
else
{
/* Trying to find a triplet with the next value */
n++;
}
}
/* printing the list of coprime triplets */
printf("\n");
for (int i = 0; i < ntrip; i++)
{
printf("%2d ", coprime[i]);
if ((i+1) % 10 == 0)
{
printf("\n");
}
}
printf("\n\nNumber of elements in coprime triplets: %d\n\n", ntrip);
return 0;
}</lang>
{{out}}
<pre> 1 2 3 5 4 7 9 8 11 13
6 17 19 10 21 23 16 15 29 14
25 27 22 31 35 12 37 41 18 43
47 20 33 49 26 45
Number of elements in coprime triplets: 36</pre>
=={{header|Delphi}}==
Line 640 ⟶ 753:
47 20 33 49 26 45
</pre>
=={{header|Python}}==
<lang Python>
########################
# #
# COPRIME TRIPLETS #
# #
########################
#Starting from the sequence a(1)=1 and a(2)=2 find the next smallest number
#which is coprime to the last two predecessors and has not yet appeared in
#the sequence.
#p and q are coprimes if they have no common factors other than 1.
#Let p, q < 50
#Function to find the Greatest Common Divisor between v1 and v2
def Gcd(v1, v2):
a, b = v1, v2
if (a < b):
a, b = v2, v1
r = 1
while (r != 0):
r = a % b
if (r != 0):
a = b
b = r
return b
#The first two values
a = [1, 2]
#The next value candidate to belong to a triplet
n = 3
while (n < 50):
gcd1 = Gcd(n, a[-1])
gcd2 = Gcd(n, a[-2])
#if n is coprime of the previous two value and isn't present in the list
if (gcd1 == 1 and gcd2 == 1 and not(n in a)):
#n is the next element of a triplet
a.append(n)
n = 3
else:
#searching a new triplet with the next value
n += 1
#printing the result
for i in range(0, len(a)):
if (i % 10 == 0):
print('')
print("%4d" % a[i], end = '');
print("\n\nNumber of elements in coprime triplets = " + str(len(a)), end = "\n")
</lang>
{{out}}
<pre>
1 2 3 5 4 7 9 8 11 13
6 17 19 10 21 23 16 15 29 14
25 27 22 31 35 12 37 41 18 43
47 20 33 49 26 45
Number of elements in coprime triplets = 36</pre>
=={{header|Raku}}==
| |||