Zsigmondy numbers: Difference between revisions
Added C# example
(→{{header|ALGOL 68}}: Slight optimisation) |
(Added C# example) |
||
Line 334:
2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 3077713 115933787267041 30133 5689910849522509 3949201
</pre>
=={{header|C sharp|C#}}==
{{trans|Java}}
<syntaxhighlight lang="csharp">
internal class Program
{
private static void Main(string[] args)
{
//record Pair(int a, int b) { }
List<KeyValuePair<int, int>> pairs =
[
KeyValuePair.Create(2, 1),
KeyValuePair.Create(3, 1),
KeyValuePair.Create(4, 1),
KeyValuePair.Create(5, 1),
KeyValuePair.Create(6, 1),
KeyValuePair.Create(7, 1),
KeyValuePair.Create(3, 2),
KeyValuePair.Create(5, 3),
KeyValuePair.Create(7, 3),
KeyValuePair.Create(7, 5),
];
foreach (KeyValuePair<int, int> pair in pairs)
{
Console.WriteLine("Zsigmondy(n, " + pair.Key + ", " + pair.Value + ")");
for (int n = 1; n <= 18; n++)
{
Console.Write(ZsigmondyNumber(n, pair.Key, pair.Value) + " ");
}
Console.WriteLine();
}
}
private static long ZsigmondyNumber(int n, int a, int b)
{
long dn = (long)(Math.Pow(a, n) - Math.Pow(b, n));
if (IsPrime(dn))
{
return dn;
}
List<long> divisors = Divisors(dn);
for (int m = 1; m < n; m++)
{
long dm = (long)(Math.Pow(a, m) - Math.Pow(b, m));
divisors.RemoveAll(d => GCD(dm, d) > 1);
}
return divisors[divisors.Count() - 1];
}
private static List<long> Divisors(long number)
{
List<long> result = new List<long>();
for (long d = 1; d * d <= number; d++)
{
if (number % d == 0)
{
result.Add(d);
if (d * d < number)
{
result.Add(number / d);
}
}
}
result.Sort();
return result;
}
private static bool IsPrime(long number)
{
if (number < 2)
{
return false;
}
if (number % 2 == 0)
{
return number == 2;
}
if (number % 3 == 0)
{
return number == 3;
}
int delta = 2;
long k = 5;
while (k * k <= number)
{
if (number % k == 0)
{
return false;
}
k += delta;
delta = 6 - delta;
}
return true;
}
private static long GCD(long a, long b)
{
while (b != 0)
{
long temp = a; a = b; b = temp % b;
}
return a;
}
}
</syntaxhighlight>
{{out}}
<pre>
Zsigmondy(n, 2, 1)
1 3 7 5 31 1 127 17 73 11 2047 13 8191 43 151 257 131071 19
Zsigmondy(n, 3, 1)
2 1 13 5 121 7 1093 41 757 61 88573 73 797161 547 4561 3281 64570081 703
Zsigmondy(n, 4, 1)
3 5 7 17 341 13 5461 257 1387 41 1398101 241 22369621 3277 49981 65537 5726623061 4033
Zsigmondy(n, 5, 1)
4 3 31 13 781 7 19531 313 15751 521 12207031 601 305175781 13021 315121 195313 190734863281 5167
Zsigmondy(n, 6, 1)
5 7 43 37 311 31 55987 1297 46873 1111 72559411 1261 2612138803 5713 1406371 1679617 3385331888947 46441
Zsigmondy(n, 7, 1)
6 1 19 25 2801 43 137257 1201 39331 2101 329554457 2353 16148168401 102943 4956001 2882401 38771752331201 117307
Zsigmondy(n, 3, 2)
1 5 19 13 211 7 2059 97 1009 11 175099 61 1586131 463 3571 6817 129009091 577
Zsigmondy(n, 5, 3)
2 1 49 17 1441 19 37969 353 19729 421 24325489 481 609554401 10039 216001 198593 381405156481 12979
Zsigmondy(n, 7, 3)
4 5 79 29 4141 37 205339 1241 127639 341 494287399 2041 24221854021 82573 3628081 2885681 58157596211761 109117
Zsigmondy(n, 7, 5)
2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 3077713 115933787267041 30133
</pre>
| |||