3. Wer kann die schnellsten Primzahlen?

Wer kann die schnellsten Primzahlen?

  • ?

    Optimizer schrieb:

    Nein, kann ich nicht. 😑
    😉

    😃

    0
  • O

    FireFlow schrieb:

    Wooh stimmt ich hab über das Sieb was gefunden hab aber keine Implementation. Wär super wenn du mal immer so von 10^n die Anzahl angibst. 1Mrd reicht ja als Obergrenze. Wenn mein Programm bis dahin und darüber stichprobebartig korrekt arbeitet gehe ich davon aus dass es klappt.

    nein, kannst du nicht. eine milliarde ist nur ein winzig kleiner bruchteil von der 64bit reichweite die hier gefordert ist, dh wenn dein schätz algo irgendeine minimalabweichung hat, finden wir die spätestens nach der veröffentlichung des codes 😉

    übrigens braucht man maximal eine minute, um folgenden link bei google zu bekommen:

    http://www.utm.edu/research/primes/howmany.shtml

    0
  • V

    Der Generator ist vorläufig fertig.

    Er hat eine Periode von 2^64.
    Er bringt die Zahlen in folgender Verteilung:

    <10: 0.00924%
<100: 0.09225%
<1000: 0.93736%
<10000: 6.20014%
<100000: 12.5577%
<1000000: 19.0556%
<10000000: 25.3772%
<100000000: 31.7213%
<1000000000: 38.1788%
<10000000000: 44.5419%
<100000000000: 50.9001%
<1000000000000: 57.3257%
<10000000000000: 63.7329%
<100000000000000: 70.0624%
<1000000000000000: 76.4963%
<10000000000000000: 82.874%
<100000000000000000: 89.1879%
<1000000000000000000: 95.4239%

    Das ist die Ausgabe folgenden Messprogramms:

    #include <iostream>
using namespace std;

typedef long long i64;

int main()
{
    //diese werte werden normalerweise eingelesen
    i64 randa=123;
    i64 randb=456;
    i64 randx=789;
    i64 count=10000000;

    //macht die periode des zufallszahlengenerators lang
    randa=2*randa+1;
    randb=4*randb+1;

    for(i64 max=10;max>0;max=max*10){
        i64 c=0;
        for(i64 i=0;i<count;++i){
            randx=randx*randa+randb;
            i64 n=(randx&0x7fffffff80000000LL)>>31;
            randx=randx*randa+randb;
            n=n|(randx&0x7fffffff00000000LL);
            randx=randx*randa+randb;
            int shift=(randx&0x7fffffff00000000LL)>>32;
            n=n>>(shift%52);

            if(n<max) ++c;

        }
        cout<<"<"<<max<<": "<<c/double(count/100)<<'%'<<endl;
    }
	return 0;
}

    Um Zu testen, ob der Generator bei Euch funktioniert, nehmt vielleicht

    #include <iostream>
using namespace std;

typedef long long i64;

int main()
{
    //diese werte werden normalerweise eingelesen
    i64 randa=123;
    i64 randb=456;
    i64 randx=789;
    i64 count=100000;

    //macht die periode des zufallszahlengenerators lang
    randa=2*randa+1;
    randb=4*randb+1;

    i64 test=0;
    for(i64 i=0;i<count;++i){
        randx=randx*randa+randb;
        i64 n=(randx&0x7fffffff80000000LL)>>31;
        randx=randx*randa+randb;
        n=n|(randx&0x7fffffff00000000LL);
        randx=randx*randa+randb;
        int shift=(randx&0x7fffffff00000000LL)>>32;

        n=n>>(shift%52);
        test+=n%1000000*i;
    }
    cout<<test<<endl;
    return 0;
}

    Ausgabe:
    2153201463864000

    Das Hauptprogramm soll dann so aussehen:

    int main()
{
    //diese werte werden normalerweise eingelesen
    i64 randa=123;
    i64 randb=456;
    i64 randx=789;
    i64 count=100;

    //zum normalen testen einfach folgende zeile auskommentieren
    cin>>randa>>randb>>randx>>count;

    //macht die periode des zufallszahlengenerators lang
    randa=2*randa+1;
    randb=4*randb+1;

    i64 ergebnis=0;
    for(i64 i=0;i<count;++i){
        randx=randx*randa+randb;
        i64 n=(randx&0x7fffffff80000000LL)>>31;
        randx=randx*randa+randb;
        n=n|(randx&0x7fffffff00000000LL);
        randx=randx*randa+randb;
        int shift=(randx&0x7fffffff00000000LL)>>32;

        n=n>>(shift%52);
        if(isPrime(n)){
            ++ergebnis;
//            cout<<n<<endl;
        }
    }
    cout<<ergebnis<<endl;
	return 0;
}

    es gibt bei mir

    6

    aus, wenn ich die standardwerte lasse.

    0
  • O

    aha...also ist es nicht erlaubt, die werte nach der generierung zu sortieren...schade 😞

    0
  • V

    otze schrieb:

    aha...also ist es nicht erlaubt, die werte nach der generierung zu sortieren...schade 😞

    doch, klaro.
    das "Das Hauptprogramm soll dann so aussehen:" war nicht würtlich zu nehmen.
    "das hauptprogramm soll dann so aussehen oder eine ausgabe erzeugen, die gleich ist, ganz völlig egal, wie ihr das hinkriegt".

    0
  • V

    ein weiteres ergebnis:
    echo 1234 4711 8000 1000 | fpc.exe
    gibt bei mir
    55
    aus.

    0
  • V

    bringt euren code einfach zum treffen mit.
    wer nicht kommt, kann auch nach volkard@gmx.net schicken.

    0
  • V

    der gewinner ist 0xdeadbeef.

    der gewinnercode:

    /*	$NetBSD: pr_tbl.c,v 1.7 2003/08/07 09:37:33 agc Exp $	*/

/*
 * Copyright (c) 1989, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Landon Curt Noll.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <stdio.h>

unsigned long const primes[] = {
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,
...und so weiter...
65407,65413,65419,65423,65437,65447,65449,65479,65497,65519,65521,65537,0
};

bool isPrime(unsigned long long x) {
  unsigned long long i;
  unsigned j;

  if(x == 2 || x == 3 || x == 5 || x == 7)
    return 1;
  if(x < 2 || x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0)
    return 0;

  if(x <= 65537 * 65537) {
    for(i = 4; primes[i] * primes[i] <= x; ++i)
      if(x % primes[i] == 0)
	return 0;
  } else {
    for(i = 4; primes[i]; ++i) 
      if(x % primes[i] == 0)
	return 0;
    j = 2;
    for(i = primes[i - 1] + 2; i * i <= x; i += (j = 6 - j))
      if(x % i == 0)
	return 0;
  }

  return 1;
}
//nebst der main, die schon gepostet wurde
    0
  • ?

    Wer hat überhaupt alles mitgemacht?

    0
  • V

    interessanter wäre... schrieb:

    Wer hat überhaupt alles mitgemacht?

    nur er.

    0
  • ?

    ROFLMAO! 🤡

    0
  • B

    Schlägt er denn deine Variante, volkard?

    0
  • J

    Nein, ziemlich sicher nicht. Hier werden ja relativ stupide alle Teiler getestet. Miller-Rabin (auch entrandomisiert) kann da aber was rausholen.

    0
  • O

    ok, meine version wär schneller gewesen 🙄

    0
  • V

    otze schrieb:

    ok, meine version wär schneller gewesen 🙄

    warum haste nicht eingeschickt?

    0
  • ?

    bestimmt weil er dachte jester macht mit. :p

    0
Anmelden zum Antworten