C++ Prime Number Algorithm

>>7

Thank you. I did notice that. Here is a slightly updated version of the code. While it still does not produce the desired outfit, it is a step up from what it was before hand. I am not exactly sure if I understand exactly where you are coming from with the not initializing PrimeStatus.


#include <iostream>
using namespace std;

int main()
{
    long PrimeStatus[100001];
    long MAX_PRIME_CHECK = 100000;

    for(int s = 1; s < MAX_PRIME_CHECK; s++)
    {
        if(s > 2)
        {
            PrimeStatus[s] == 0;
            return 0;
        }
       
        else if(s <= 2)
        {
            if(PrimeStatus[s] == 1)
            {
                PrimeStatus[s] == 1;
            }
           
            else if(PrimeStatus[s] == 0)
            {
                if(s%(s-1) == 0)
                {
                    PrimeStatus[s] == 1;
                }
               
                else while(s%(s-1) != 0)
                {
                    s = s-1;
                }
               
                if(s%(s-1) == 0)
                {
                    PrimeStatus[s] == 1;
                }
            }
        }
       
        if(PrimeStatus[s] == 0)
        {
            cout << s << endl;
        }
    }
}


    public static void CalcPrimeFactors(long integer) {
        boolean state;
        long divrem, userint = integer;
        for(long i = 2; state == true; i++) {
            divrem = userint % i;
            if(divrem == 0) {
                userint /= i;
                i--;
            }
            else if (userint == 1)
                state = false;
        }
    }

int
main (void)
{
  printf("%s, %s %s %s!",
    "Hey", "fuck", "you", "bitch");
  return 0;
}

Leah Culver, is it you? Give me a sign, Leah. _{I love you.}

>>10

This looks quite useful. I'll come back with results. Thank you.

>>11

Despite the utter lack of general maturity amongst most of us, at least be somewhat subtle about it. Also, could very well do that with a simple string if you want to be that blunt.

>>12

...my fail.

(10 -- 9; 11 -- 10)

>>11

Sorry, keep looking~

(No results just yet. A few minutes.)

I have formally verified your code.

>>14
yeah I just tested it on an ARM9E processor and it worked fine.  looks like you've stumbled onto a bug on whatever you're using.  grats.

>>14 & >>15

Are you meaning the code at >>8 ? Or with the addition of the code at >>9 ?

With the code at 8, I only run into zeros as the output, and I am still relatively new at this that I have not exactly been able to implement 9.

Sieve of Eratosthenes

WHBTC

>>10
I have formally verified your code. The output is ALWAYS the same: Hey, fuck you bitch! Bravo!

Drop out and work at McDonalds. That is all you are good for.

Yuck, OP's code hurts to look at.

(define (square x) (* x x))

(define (miller-rabin-expmod base exp m)
  (define (squaremod-with-check x)
    (define (check-nontrivial-sqrt1 x square)
      (if (and (= square 1)
               (not (= x 1))
               (not (= x (- m 1))))
          0
          square))
    (check-nontrivial-sqrt1 x (remainder (square x) m)))
  (cond ((= exp 0) 1)
        ((even? exp) (squaremod-with-check
                      (miller-rabin-expmod base (/ exp 2) m)))
        (else
         (remainder (* base (miller-rabin-expmod base (- exp 1) ))
                    m))))
(define (miller-rabin-test n)
  (define (try-it a)
    (define (check-it x)
      (and (not (= x 0)) (= x 1)))
    (check-it (miller-rabin-expmod a (- n 1) n)))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((miller-rabin-test n) (fast-prime? n (- times 1)))
        (else false)))

(define (prime? n) 
    ; Perform the test how many times? 
    ; Use 100 as an arbitrary value. 
    (fast-prime? n 100))

(define (prime-status n)
 (define (prime-status-iter m n)
  (cond ((> m n) '())
        (else (begin
                (fast-prime? m 100)
                (prime-status-iter (+ m 1) n)))))
 (prime-status-iter 1 n))

(prime-status 100000)

>>21
Now all OP has to do is implement Scheme in Sepples.

>>22
boost::scheme

This, too, looks like a job for Haskell: The Ironic Hipster Programming Language.

>>21
Fuck your parentheses toy language.

>>25
No, fuck you..

>>25
your
hurr

>>27

hurr

Back to /b/, please

Let a prime number be a number that has no factors aside from one and itself.

A number only has factors that complement eachother, meaning they come in pairs. Thus, you only need to look for factors prior to n / 2.

I'm not exactly sure what you mean by a "prime number algorithm," if you mean it determines a number that's prime or if it generates prime numbers, either of these can be achieved through the use of a prime number function.

bool isPrime(int n) {
    bool is = true;
    for (int c = 2; c <= (n / 2); c++) { // lul sepples
        if ((n % c) == 0) { // c is a factor
            is = false;
            break;
        }
    }
    return is;
}

If you need to generate primes, simply iterate through your range of numbers until a sufficient number of primes is generated. You could alternatively change this to return a vector and push the factors in if you wanted to for some other assignment.

Happy Sepples.

>>29
As an afterthought, I'd modify this a bit.

bool isPrime(int n) {
    if (n <= 1)
        return false;
    bool is = true;
    for (int c = 2; c <= (n / 2); c++) { // lul sepples
        if ((n % c) == 0) { // c is a factor
            is = false;
            break;
        }
    }
    return is;
}

>>29
Close, but not n/2, rather sqrt(n) as the upper limit.
Also just test with all previously discovered primes, not every integer.

>>29
>Thus, you only need to look for factors prior to n / 2.
sqrt( n )

>>31
Also just test with all previously discovered primes, not every integer.
Don't do this, you might miss one of the factors.

>>33
You won't get a complete factorization, but that's not what is wanted.  If a number is composite, one of its factors will be a prime no larger than its square root; so if you get no factors, the number has to be prime.

>>34
Citation needed

This uses the Sieve of Eratosthenes and an assload of memory for speed purposes. It can be further optimized, but this version gets the point across.
I look forward to having it submitted to entry level C/C++ classes across the nation.


#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

_Bool isNumeric (char[]);


int main (int argc, char *argv[])
{
        int m, index;
        unsigned long size;
        _Bool *primes;

        // Check supplied arguments
        if (argc < 2)
        {
                fprintf (stderr, "No maximum size specified, using 1,000,000...\n");
                size = 1000000;
        }
        else
        {
                if (isNumeric (argv[1]))
                        size = atoi (argv[1]);
                else
                {
                        fprintf (stderr, "Maximum size must be numeric.\n");
                        return 1;
                }
        }

        // Allocate a zeroed block of memory
        primes = (_Bool *) calloc (size, sizeof(*primes));
        if (primes == NULL)
        {
                fprintf (stderr, "Failed to allocate enough memory, maximum size too large!\n");
                return 1;
        }

        // Main loop
        printf ("Calculating primes for digits 0 -> %i...\n\n", size);
        for (index = 2; index < size; index++)
        {
                if (primes[index] == 0)
                {
                        printf ("%i\n", index);
                        for (m = 2 * index; m < size; m += index)
                                primes[m] = 1;
                }
        }
        free (primes);

        printf ("\nFinished calculating primes for digits 0 -> %i\n", size);

        return 0;
}


// Determines if a character string is numeric
_Bool isNumeric (char str[])
{
        int i;
        for (i = 0; i < strlen(str); i++)
        {
                if (!isdigit (str[i]))
                        return 0;
        }

        return 1;
}

_Bool?

What the fuck.

>>35
It's a trivial deduction from the Sieve of Eratosthenes; or you get it by simple induction.

If a number is composite one of its factors is a number less than its square root.  Either that factor is prime, in which case the assertion is proved, or composite, in which case we repeat the process on that factor.  Since the sequence is strictly monotonic and bounded below, the decomposition must terminate.

>>38
In English please, lol. I understood 'factor' and 'prime', but not much else. One hint I learnt from an interviewer was try to explain it to your grandmother, or your 5 year old niece.

>>39
Your grandmother and your 5 year old niece haven't read SICP.