Доброго времени суток, господа)
Учусь на первом курсе на втором семестре, по алгоритмам появилась такая задача->подать более быстрый способ поиска простых чисел и сравнить его с тем что есть. Этот первоначальный поиск:
static bool IsPrime(BigInteger num)
{
modulo = 1;
if (num < 2) return false;
else if (num < 4) return true;
else if (num % 2 == 0)
{
modulo++;
return false;
}
else for (BigInteger u = 3; u < num / 2; u += 2)
{
if (num % u == 0)
{
return false;
}
modulo++;
}
return true;
}
вот мое решение
using System;
using System.Numerics;
using System.Diagnostics;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Project2._0
{
class Program
{
static long modulo;
static long modulo1;
static void Main(string[] args)
{
BigInteger[] Array = { 100913, 1009139, 10091401, 100914061 , 1009140611 , 10091406133, 100914061337, 1009140613399 };//
Console.WriteLine("Test IsPrime");
TestFirstAlgorytm(Array);
Console.WriteLine("Test IsPrime2");
TestSecondAlgorytm(Array);
}
static void TestFirstAlgorytm(BigInteger[] Array)
{
for (int i = 0; i <= 7; i++)
{
BigInteger num = Array[i];
long StartingTime = Stopwatch.GetTimestamp();
IsPrime(num);
long EndingTime = Stopwatch.GetTimestamp();
long ElapsedTime = EndingTime - StartingTime;
double ElapsedSeconds = ElapsedTime * (1.0 / Stopwatch.Frequency);
Console.WriteLine("Count:{0}\tTime:{1} \tTest:{2}\tArray:{3}", modulo, ElapsedSeconds, IsPrime(num), Array[i]);
}
}
static void TestSecondAlgorytm(BigInteger[] Array)
{
for (int i = 0; i <= 7; i++)
{
BigInteger num = Array[i];
long StartingTime = Stopwatch.GetTimestamp();
IsPrimeImproved(num);
long EndingTime = Stopwatch.GetTimestamp();
long ElapsedTime = EndingTime - StartingTime;
double ElapsedSeconds = ElapsedTime * (1.0 / Stopwatch.Frequency);
Console.WriteLine("Count:{0}\tTime:{1} \tTest:{2}\tArray:{3}", modulo1, ElapsedSeconds, IsPrime(num), Array[i]);
}
}
static bool IsPrime(BigInteger num)
{
modulo = 1;
if (num < 2) return false;
else if (num < 4) return true;
else if (num % 2 == 0)
{
modulo++;
return false;
}
else for (BigInteger u = 3; u < num / 2; u += 2)
{
if (num % u == 0)
{
return false;
}
modulo++;
}
return true;
}
static bool IsPrimeImproved(BigInteger num)
{
modulo1 = 0;
// int _sqrt_int = (int)Math.Sqrt((double)num); //Целая часть от квадратного корня из d
if (num < 2) return false;
else if (num < 4) return true;
else if (num % 2 == 0)
{
modulo++;
return false;
}
else
for (BigInteger i = 3; i*i <= num; i+=2)
{
modulo1++;
if ((num % i) == 0) //Проверка: остаток от деления d/i==0?
return false;
}
return true;
}
}
}
но есть проблема: Отдельно первый алгоритм работает, а в собранном виде
нет. Всем кто поможет и укажет на мои ошибки, буду очень благодарен!
