// Arup Guha
// 11/7/2014
// Code for solution to Homework 5c Question 1

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 1000

void pick(int* ptrA, int*ptrB, int prime);
int count(int prime, int a, int b);

int main() {

    srand(time(0));

    // Set up prime sieve.
    int i, j, isPrime[SIZE];
    isPrime[0] = 0;
    isPrime[1] = 1;
    for (i=2; i<SIZE; i++)
        isPrime[i] = 1;

    // Run prime sieve.
    for (i=2; i<SIZE; i++)
        for (j=2*i; j<SIZE; j+=i)
            isPrime[j] = 0;

    // Go through each prime.
    for (i=20; i<SIZE; i++) {
        if (isPrime[i]) {

            // Get a valid a and b.
            int a, b, prime = i;
            pick(&a,&b, prime);
            while (4*a*a*a % prime == 27*b*b % prime)
                pick(&a, &b, prime);

            // Count points and print.
            int numPts = count(i,a,b);
            printf("%d\t%d\n",i, numPts);
        }
    }
}

// Pick a random a and b and set them from 0 to p-1.
void pick(int* ptrA, int*ptrB, int prime) {
    *ptrA = rand()%prime;
    *ptrB = rand()%prime;
}

int count(int prime, int a, int b) {

    // Brute Force Loop - count all valid points.
    int x, y, cnt=1;
    for (x = 0; x < prime; x++)
        for (y = 0; y < prime; y++)
            if (y*y % prime == (x*x*x +a*x+b) % prime)
                cnt++;
    return cnt;
}