Oppgave 3

  public static int[] primtall(int n)
  {
    if (n < 2) return new int[0];  // ingen primtall mindre enn 2

    boolean[] sammensatt = new boolean[n+1];

    for (int k = 3; k*k <= n; k += 2)
    {
      if (!sammensatt[k])                     // k er et primtall
        for (int i = k*k; i <= n; i += 2*k)   // øker med 2k
          sammensatt[i] = true;               // i er et multippel av k
    }

    int antall = 1;
    for (int k = 3; k <= n; k += 2)           // teller opp primtallene
    {
      if (!sammensatt[k]) antall++;
    }

    int[] primtall = new int[antall];
    primtall[0] = 2;

    for (int i = 1, k = 3; i < antall; k += 2)
    {
      if (!sammensatt[k]) primtall[i++] = k;
    }

    return primtall;
  }  

Oppgave 4

  public static int antallPrimtall(int n)
  {
    if (n < 2) return 0;

    BitSet sammensatt = new BitSet(n + 1);

      for (int k = 3; k*k <= n; k += 2)
      {
        if (!sammensatt.get(k))
          for (int i = k * k; i <= n; i += 2*k)
            sammensatt.set(i);
      }

    return (n+1)/2 - sammensatt.cardinality();
  }

Oppgave 5

  public static int maksPrimtall(int n)
  {
    if (n < 2) throw new
      NoSuchElementException("Ingen primtall <= " + n);

    boolean[] sammensatt = new boolean[n+1];

    for (int k = 3; k*k <= n; k += 2)
    {
      if (!sammensatt[k])
        for (int i = k*k; i <= n; i += 2*k)
          sammensatt[i] = true;
    }

    int k = (n & 1) == 0 ? n - 1 : n;
    for ( ; k > 2; k -= 2)
      if (!sammensatt[k]) return k;

    return 2;
  }