C#: Fermats primtallstest feiler når n > 13

[hockey500]

Hei,

begynte akkurat på Project Euler, hvor en del av de enkleste oppgavene går ut på å finne sum av primtallsrekker o.l. Derfor tenke jeg at jeg skulle prøve en litt mer effektiv algoritme enn å teste for alle tall mindre enn Math.Floor(Math.Sqrt(n)) + 1. Testet Fermats primtallstest, som funket meget flott, så lenge tallet n er mindre enn 15

 

		public static bool IsPrime(int n, int k)
	{
		n = Math.Abs(n);

		if (n < 2)
			return false;
		else
		{
			Random r = new Random();
			int a;

			for (int i = 0; i < k; i++)
			{
				a = r.Next(1, n - 1);
				if ((Math.Pow(a, n - 1) % n) != 1)
					return false;
			}
			return true;
		}
	}

koden er sikkert ikke perfekt, og algoritmen er faktisk ubrukelig i mitt tilfelle, men når jeg ikke fikk den til å funke ble jeg litt nysgjerrig på hvorfor. Noen som kan fortelle meg hva som er galt med den?

 

EDIT: det er vel Math.Pow()-delen som blir litt for stor, så jeg må rett og slett lage min egen klasse for å håndtere så store tall?

Endret 24. mars 2008 av hockey500

[Mr.Garibaldi]

Det finnes større tall enn int...

int bruker 32 bits, og har en range fra -2 147 483 648 til 2 147 483 647.

Du kan bruke unsigned int (siden du ikke har noen negative tall) som gir

uint 32 bits, range 0 til 4 294 967 295

Ellers har du long

long 64 bits, range -9 223 372 036 854 775 808 til 9 223 372 036 854 775 807

ulong 64 bits, range 0 til 18 446 755 073 709 551 615

 

Så tviler på at du trenger å lage en egen klasse for å håndtere størrelsen på tallet......

[MirusMentis]

regner med at det er den oppgaven der du skal summere alle primtall under 2mill?

 

Jeg brukte først denne koden:

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;



class MainClass
{
public static void Main()
{
	int num;
	int i;
	int factor;
	bool isprime;
	long sum = 0;
	int tallnr = 0;
	int y= 0;
	Stopwatch sw = new Stopwatch();
	sw.Start();
	for (num = 2; num <120000; num++)
	{
		isprime = true;


		// see if num is evenly divisible 
		for (i = 2; i <= num / 2; i++)
		{
			if ((num % i) == 0)
			{
				// num is evenly divisible -- not prime 
				isprime = false;	   
			}
		}

		if (isprime)
		{
			sum += num;
			Console.Write("Primtall: " + num);
			y++;
			Console.WriteLine(" Dette var primtall nr: " + y);
			if (y==10001)
			{
				tallnr = y;
				break;
			}
		}
	}

	sw.Stop();
	 TimeSpan ts = sw.Elapsed;

	// Format and display the TimeSpan value.
	string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",
		ts.Hours, ts.Minutes, ts.Seconds,
		ts.Milliseconds / 10);
	Console.WriteLine("Tid brukt: "+ elapsedTime);
	Console.WriteLine("Summen er " +sum);
		Console.WriteLine("tall 10001 er: "+tallnr);
	Console.ReadLine();
}
}

 

Denne brukte ca 5 timer på oppgaven.. Men så jukset jeg litt og fant en kode noen andre har laget.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace nysumprimes
{
class Program
{

	static bool IsPrime(long x)
	{
		double sqr = Math.Sqrt(x);

		if (x == 2)
			//Console.WriteLine(x);
			return true;
		if (x % 2 == 0)
			return false;
		for (int i = 3; i <= sqr + 1; i += 2)
			if (x % i == 0)
				return false;
		return true;
	}

	static long PrimeSum(long until)
	{
		long sum = 2;

		for (long i = 3; i < until; i += 2)
			if (IsPrime(i))
				sum += i;
		return sum;
	}

	static void Main(string[] args)
	{
		Stopwatch sw = new Stopwatch();
		sw.Start();
		Console.WriteLine(PrimeSum(2000000));
		sw.Stop();
		TimeSpan ts = sw.Elapsed;
		string tidbrukt = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",
	   ts.Hours, ts.Minutes, ts.Seconds,
	   ts.Milliseconds / 10);
		Console.WriteLine("Tid brukt: "+tidbrukt);
		Console.ReadLine();
	}

 

Denne kjører på ca 2-3sekunder.

Endret 31. mars 2008 av Pjukern

[hockey500]

Det var faktisk ikke det å løse problemet som var utfordringen, tenkte bare å finne en litt mer effektiv måte å gjøre det på. Min kode brukte 5 sek.