Oversæt matematisk algoritme til kode, meget svær opgave

sådan noget tis, den kan ikke vise tegnene rigtigt

Smid den ind her og poste et link:
http://www.pastebin.com/

Det er formlem midt på:
  http://www.utm.edu/research/primes/prove/prove4_3.html
ikke ?

Den er også her (samt analyse af problemstillingen)
http://www.eas.asu.edu/~cse450sp/projects/final_P12.doc

jepper præcist arne_v, og den kunne jeg godt tænke mig at få lavet om til C# kode

viciodk, det blev de samme da jeg forsøgte at skrive på den side

For normale int eller for vilkårligt store integers ?

hmm, er det ikke nemmest at starte med normale int

og har lige uploadet algoritmen som pdf her
http://www.gulbaek.net/tmp/algoritme.pdf

Jo

(og den er svær nok i forvejen)

hehe jo tak, er også villig til at give flere point

Du må ikke give mere end 200 point, så det kan du ikke.

Men der er jo også lidt udfording i det !

:-)

hehe ja, det er en rimelig stor udfordring, men tænk på hvor mange der kan få glæde af det :-)

Har lige fået lavet gcd metoden, så det er da en start

public static int gcd(int a, int b)
        {
            int x = a;
            int y = b;
            while (y != 0)
            {
                int r = x % y;
                x = y;
                y = r;
            }
            return x;
        }

Her er hvad jeg har fået lavet indtil videre, umiddelbart virker den fint, men jeg mangler stadig at implementer lidt.

using System;

namespace Primtal_i_P
{
    class Class1
    {
        [STAThread]
        static void Main(string[] args)
        {
            prime(Convert.ToInt32(Console.ReadLine()));
            //Console.WriteLine(gcd(414,662));
            Console.ReadLine();
        }
        public static int gcd(int a, int b)
        {
            int x = a;
            int y = b;
            while (y != 0)
            {
                int r = x % y;
                x = y;
                y = r;
            }
            return x;
        }

        public static bool prime(int n)
        {
            //if(n is of the form a^b, b > 1) output COMPOSITE;
            int    r = 2;
            while( r < n)
            {
                if(gcd(n,r) != 1)
                {
                    Console.WriteLine(n +" er ikke et primtal");
                    return false;
                }
                else
                {
                    int q = 1;  // let q be the largest prime factor of r - 1
                    if(q >= 4*Math.Sqrt(r * Math.Log(n)) & (n*((r-1)/q) != 1 % r))
                        break;
                }
                r++;
            }
            int a = 1;
            if(a == 2 * Math.Sqrt( r * Math.Log(n)))
                //if( ((x-a)^n != (x^n - a)) % x^r - 1)
            {
                    Console.WriteLine(n +" er ikke et primtal");
                    return false;
            }
            Console.WriteLine(n +" er et primtal");
            return true;
        }

    }
}

de udmærkerede steder er de steder hvor de driller lidt, f.eks. aner jeg ikke hvor x kommer fra i den sidste if sætning.

Der er ikke nogen, der kan forklare hvad dette betyder ?

if(n is of the form a^b, b > 1) output COMPOSITE;

Forklare det er nemt. Kode det ...

2^2 = 4
2^3 = 8
2^4 = 16
...
3^2 = 9
3^3 = 27
3^4 = 81
...
...

Er ikke primtal.

Hmm, ja det blir jo lidt svært at kode, men det må være muligt

public static bool isAB(int n)
    {
        for(int a = 2; a <= (int)Math.Sqrt(n); a++)   
        {
            for(int b = 2; b <= (int)(Math.Log(n)/Math.Log(a)); b++)
            {
                if(Math.Pow(a, b) == n)
                {
                    return true;
                }
            }
        }
        return false;
    }

ligner en ide !

hmm, har lige kørt nogle tests med og uden din kode, hvis jeg skal finde alle primtal fra 1 -> 1000 så er det en del hurtigere med din kode, men hvis jeg forsøger mig med 1 -> 10000 så blir det faktisk langsommere

Den skal nok omkodes en del, så man helt undgår de meget dyre Sqrt/Log/Pow.

hmm,ja det ville nok være en god ide

Men hvad så med denne linie.

if( ((x-a)^n != (x^n - a)) % x^r - 1)

aner ikke lige hvor x kommer fra.

Et af stederne bruger de 3 vandrette streger, hvilket antyder at x er
"for enhver x".

Ja.

using System;

class MainClass
{
    private const int N = 200000;
    public static bool isAB1(int n)
    {
        for(int a = 2; a <= (int)Math.Sqrt(n); a++)   
        {
            for(int b = 2; b <= (int)(Math.Log(n)/Math.Log(a) + 0.01); b++)
            {
                if(Math.Pow(a, b) == n)
                {
                    return true;
                }
            }
        }
        return false;
    }
    public static bool isAB2(int n)
    {
        int a = 2;
        while(a*a <= n)
        {
            int apowb = a * a;
            while(apowb <= n)
            {
                if(apowb == n)
                {
                    return true;
                }
                apowb *= a;
            }
            a++;
        }
        return false;
    }
    public static void Main(string[] args)
    {
        for(int i = 2; i <= 1000; i++)
        {
            if(isAB1(i) != isAB2(i))
            {
                Console.WriteLine(i + " " + isAB1(i) + " " + isAB2(i));
            }
        }
        long t1 = DateTime.Now.Ticks;
        for(int i = 2; i < N; i++)
        {
            isAB1(i);
        }
        long t2 = DateTime.Now.Ticks;
        long t3 = DateTime.Now.Ticks;
        for(int i = 2; i < N; i++)
        {
            isAB2(i);
        }
        long t4 = DateTime.Now.Ticks;
        Console.WriteLine("1: " + (t2 - t1)/1000000 + " 2: " + (t4 - t3)/1000000);
    }
}

siger at isAB2 er 80 gange hurtigere end isAB1.

(bemærk iøvrigt de +0.01 - det virkede ikke helt uden)

Hehe, ja det var jo lidt af en forbedring

Kunne være jeg skulle få fjernet alle de steder jeg har brugt Math.Log og Math.Sqrt

Vist ved at være lukke tid :-) Fik ikke lavet en 100 % løsning, men fint nok til mit behov, takker

arne_v og viciodk kom lige med et svar

svar