2. Решето Эратосфена для отбора простых чисел: // http://ru.wikipedia.org/wiki/%D0%E5%F8% ... 4%E5%ED%E0Olej писал(а): Ещё могу показать пару сравнений ... широко известные алгоритмы:
1. "Ханойская башня"
на C:
Код: Выделить всё
#include <stdio.h>
#include <stdlib.h>
// решето Эратосфена
// http://ru.wikipedia.org/wiki/%D0%E5%F8%E5%F2%EE_%DD%F0%E0%F2%EE%F1%F4%E5%ED%E0
typedef long long data_t;
void eratos( char *arr, ulong size ) {
ulong i, j;
for( i = 2; i < size; i++ ) // цикл по всему массиву от первого простого числа "2"
if( 1 == arr[ i ] )
for( j = i + i; j < size; j += i ) // вычеркивание всех чисел кратных i
arr[ j ] = 0;
}
int main( int argc, char **argv ) {
long n;
char debug = 0;
if( argc != 2 )
printf( "usage: %s [-]<number>\n", argv[ 0 ] ), exit( 1 );
n = atol( argv[ 1 ] ); // максимальное число
if( n < 0 ) n = -n, debug = 1;
ulong k, j;
char *a = calloc( n + 1, sizeof( char ) );
a[ 0 ] = a[ 1 ] = 0; // вычёркиваем "0" и "1"
for( k = 2; k < n; k++ ) a[ k ] = 1; // остальные размечаем как простые
eratos( a, n );
for( k = 0, j = 0; k < n; k++ )
j += ( a[ k ] != 0 ? 1 : 0 );
printf( "простых чисел %lu\n", j );
if( debug ) {
#define INLINE 10
for( k = 0, j = 0; k < n; k++ )
if( 1 == a[ k ] ) {
j++;
printf( "%lu%s", k, ( 0 == j % INLINE ? "\n" : "\t" ) );
}
if( j % INLINE != 0 ) printf( "\n" );
}
free( a );
return 0;
}
Код: Выделить всё
package main
import( "os"; "strconv" )
func main() {
type data_t int64
var срез []bool;
debug := false
eratos := func () {
count:= func () data_t {
var j data_t
for i := range срез { if срез[ i ] { j++ } }
return j
}
for i := range срез {
if срез[ i ] {
for j := i + i; j < len( срез ); j += i {
срез[ j ] = false; // вычеркивание всех чисел кратных i
}
}
}
print( "простых чисел ", count(), "\n" );
}
show := func ( s []bool ) { // диагностика среза
const inlin = 10
var j data_t
for i := range s {
if s[ i ] {
j++
print( i, "\t" )
if 0 == ( j % inlin ) { print( "\n" ) }
}
}
if( j % inlin != 0 ) { print( "\n" ) }
}
if len( os.Args ) != 2 {
print( "usage: ", os.Args[ 0 ], " [-]<number>\n" )
return
}
n, _ := strconv.Atoi( os.Args[ 1 ] )
var длина data_t = data_t( n );
if длина < 0 { длина, debug = -длина, true }
срез = make( []bool, длина )
for i := range срез { if i > 1 { срез[ i ] = true } }
eratos()
if debug { show( срез ) }
}
Код: Выделить всё
[Olej@modules erastof]$ time ./erastof_c 50000000
простых чисел 3001134
real 0m1.927s
user 0m1.897s
sys 0m0.018s
[Olej@modules erastof]$ time ./erastof_cl 50000000
простых чисел 3001134
real 0m1.966s
user 0m1.924s
sys 0m0.022s
[Olej@modules erastof]$ time ./erastof_gol 50000000
простых чисел 3001134
real 0m1.611s
user 0m1.585s
sys 0m0.025s
[Olej@modules erastof]$ time ./erastof_go 50000000
простых чисел 3001134
real 0m2.227s
user 0m2.185s
sys 0m0.023s
языках (C, C++, Lisp, D, Erlang, Java ... 2 реализации 
, Ocaml, Pascal, Python .. 2 реализации, Rexx, Ruby, Seed7).