Quelle sumliouville2.c Sprache: C

/* The Liouville function on a integer n is L(n) = (-1)^r where r is
   the number of prime factors in the prime factorization of n (L(1) = 1).
   This program is called as
           sumliouville2 begin end intlen
   and prints the sum of L(n) for n from 'begin' to 'end'. The sums are
   computed interval wise, and the length of the intervals is given as
   'intlen' (such that one can play with this length, values between
   10000 and 100000 seem to be good).

   Compile with
               gcc -O2 -Wall -g -o sumliouville2 sumliouville2.c -lm
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <math.h>

long begin, end, intlen, len, l;
char *res;
long * found;

long lsqrt(long n)
{
  double dn;
  dn = sqrt(n);
  return floor(dn);
}

inline void do_p(long p)
{
  long q, k, start;
  for (q = p; q <= end; q *= p){
    start = (-begin) % q + 1;
    if (start <= 0) start += q;
    for (k = start; k <= len; k += q){
      res[k] = -res[k];
      found[k] *= p;
    }
  }
  /*
  printf("\n"); for (k=1; k<=l; k++) printf("%ld ",(long)res[k]);
  printf("\n"); for (k=1; k<=l; k++) printf("%ld ",found[k]);
  printf("\n"); */
}

int main(int argc, char *argv[])
{
  long beginall, endall, i, k, p, n, n2, off, sum;
  char *erat, *resall;

  beginall = atol(argv[1]);
  endall = atol(argv[2]);
  intlen = atol(argv[3]);

  /* compute primes */
  n = lsqrt(endall)+1;
  n2 = n/2;
  erat = (char*) malloc((n2+1) * sizeof(char));
  for (i=0; (2*i+1)*(2*i+1) <= n; ) {
    i++;
    while (erat[i] == 1) i++;
    p = 2*i+1;
    for (k = (p*p-1)/2; k <= n2; k += p) erat[k] = 1;
  }

  /* init memory */
  l = endall - beginall + 1;
  resall = (char*) malloc((l+1)*sizeof(char));
  for(i=1; i<=l; i++) resall[i] = 1;
  found = (long*) malloc((intlen+1)*sizeof(long));

  end = beginall + intlen - 1;
  if (end > endall) end = endall;
  for (begin = beginall, res = resall; end <= endall;
                                       begin += intlen, res += intlen) {
    len = end - begin + 1;
    for(i=1; i<=len; i++) found[i] = 1;
    /* mark parity of number of prime factors */
    do_p(2);
    for (i = 1; i <= n2; i++) {
      if (erat[i] == 0) {do_p(2*i + 1); }
    }
    /* adjust if one more prime */
    off = begin-1;
    for (i=1; i<=len; i++)
      if (found[i] < off+i) res[i] = -res[i];

    /* end of next intervall */
    if (end == endall)
      end += 1;
    else {
      end += intlen;
      if (end > endall) end = endall;
    }
  }

  /* compute sum */
  sum = 0;
  for (i=1; i<=l; i++) {
    sum += resall[i];
  }
  printf("%ld\n", sum);
  return 0;
}

quality50%

¤ Dauer der Verarbeitung: 0.3 Sekunden ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.