I have seen many different forums here and elsewhere and I cannot seem to find what is wrong wit my code in particular. I have no pointers, so it can only be something with the arrays that I am using - I tried to change them and see what happens, tried to write down what is happening and when but still the error shows sometimes. I only know it has to do with memory and accessing something I am not supposed to, but cannot identify the problem - possibly more of them.
#include <stdio.h>
#include <math.h>
typedef int bool;
#define true 1
#define false 0
int main(int argc, char *argv[]){
int number;
int test;
while ((test = scanf("%d", &number)) == 1){
if (number == 0){
return 0;
}
if (number < 0){
fprintf(stderr, "Error: Chybny vstup!\n");
return 100;
}
printf("Prvociselny rozklad cisla %d je:\n", number);
if (number == 1){
printf("%d", number);
}
else{
bool prime[number+1];
for(int i = 0; i <= number; i++){
prime[i] = true;
}
for(int j = 2; j * j <= number; j++){
if (prime[j] == true){
for (int multiples = 2; prime[j * multiples] <= number; multiples++){
prime[j * multiples] = false;
}
}
}
int result[50];
int multipliers[50];
for(int i = 0; i <= 50; i++){
result[i] = 0;
}
for(int i = 0; i <= 50; i++){
multipliers[i] = 1;
}
int counter = 0;
for (int test=2; test <= number; test++){
if (prime[test]){
if (number % test == 0){
number /= test;
result[counter] = test;
counter++;
while(number % test == 0){
multipliers[counter-1]++;
number /= test;
}
}
}
}
for (int c = 0; c < counter; c++){
if (multipliers[c] > 1){
printf("%d^%d", result[c], multipliers[c]);
}
if (multipliers[c] == 1){
printf("%d", result[c]);
}
if (result[c+1] > 1){
printf(" x ");
}
}
}
printf("\n");
}
if (test == 0){
fprintf(stderr, "Error: Chybny vstup!\n");
return 100;
}
}
What you should always do, is write your program piecewise, and verify it works after completing each feature, before moving to a new one. Since you then test each feature you are implementing separately, you know that any bugs are most likely in the feature you implemented last.
In your case, this problem immediately pokes my eye:
for (int multiples = 2; prime[j * multiples] <= number; multiples++){
prime[j * multiples] = false;
}
Here, you test prime[j * multiples] <= number, i.e. compare the flag to a number. Because the late flags are zeroed till the end of the array, j*multiples will go out of bounds of the prime[] array, and eventually crash your program.
The test should be j * multiples <= number, of course.
Because I work one feature and one problem at a time, I don't know if that is the only problem your code has. Finding out is your task. If I were you, I'd write the code piecewise, perhaps sprinkling printf()s when testing, to verify each part works, so that I could rely on code I had already written, and concentrate on the part at hand, and do steady progress with minimal frustration.
There have been quite a few questions regarding Eratosthenes sieves recently. I've always found it useful to implement an abstract, dynamically allocated sieve type, and simple accessor/modifier functions to change it. Because there should only be one sieve in a program, it can be described using global variables:
#include <stdlib.h>
#include <inttypes.h>
#include <limits.h>
#include <string.h>
#include <stdio.h>
/* This is the number of bits in an unsigned long.
The exact value is floor(log(ULONG_MAX + 1)/log(2)),
but the following definition will be correct on all
modern architectures: */
#define ULONG_BITS (sizeof (unsigned long) * CHAR_BIT)
/* Prime sieve, with a flag for zero and each odd integer,
one bit per flag. */
static unsigned long *sieve = NULL;
/* Largest positive integer within the sieve. */
static uint64_t sieve_max = 4;
/* Number of unsigned longs allocated and initialized in the sieve. */
static size_t sieve_words = 0;
/* Function to discard the sieve, if no longer needed. */
static inline void sieve_free(void)
{
free(sieve); /* free(NULL); is safe, and does nothing. */
sieve = NULL;
sieve_max = 4; /* Since 0, 1, 2, 3, 4 give built-in answers */
sieve_words = 0;
}
The initial sieve_max is 4, because our is_prime() test function treats 0, 1, 2, and 3 prime, and all larger even integers non-prime anyway; that means that integers 0 through 4 are always known to our is_prime():
/* Return 1 if number is prime according to sieve,
0 if known composite/not prime. */
static inline int is_prime(const uint64_t number)
{
/* 0, 1, 2, and 3 are considered prime. */
if (number <= 3)
return 1; /* Prime */
/* All larger even integers are not prime. */
if (!(number & 1))
return 0; /* Not prime */
/* Outside the sieve? */
if (number > sieve_max) {
fprintf(stderr, "is_prime(): %" PRIu64 " is outside the sieve!\n", number);
exit(EXIT_FAILURE);
}
{
const uint64_t half = number / 2;
const size_t w = half / ULONG_BITS;
const unsigned long m = 1uL << (half % ULONG_BITS);
/* The flag for odd number is (number/2)th.
half / ULONG_BIT is the word where bit
half % ULONG_BIT is in.
Return 0 if the bit is set, 1 if clear. */
return !(sieve[w] & m);
}
}
We can very easily grow the sieve, defaulting all new flags to "not prime":
static void sieve_upto(const uint64_t max)
{
/* Number of words needed for (max+1)/2 bits. */
const uint64_t nwords = 1 + max / (2 * ULONG_BITS);
const uint64_t nbytes = nwords * (uint64_t)sizeof (unsigned long);
const size_t words = (size_t)nwords;
const size_t bytes = words * sizeof (unsigned long);
unsigned long *temp;
/* Already covered by the current sieve? */
if (sieve_max > max)
return;
/* We need to be able to handle max+1,
and neither bytes or words should overflow. */
if (max >= UINT64_MAX ||
(uint64_t)words != nwords || (uint64_t)bytes != nbytes) {
fprintf(stderr, "sieve_upto(): %" PRIu64 " is too high a maximum.\n", max);
exit(EXIT_FAILURE);
}
/* Do we already have all the bytes we need? */
if (words == sieve_words) {
sieve_max = max;
return;
}
/* Allocate/reallocate. Note that realloc(NULL, size)
is equivalent to malloc(size), so this is safe
even if 'sieve' is NULL. */
temp = realloc(sieve, bytes);
if (!temp) {
fprintf(stderr, "Not enough memory for a sieve up to %" PRIu64 ".\n", max);
exit(EXIT_FAILURE);
}
sieve = temp;
/* Clear the new words to all zeros. */
memset(sieve + sieve_words, 0, (words - sieve_words) * sizeof (unsigned long));
sieve_max = max;
sieve_words = words;
}
Finally, we need a function that will mark a number composite (not prime):
static inline void not_prime(const uint64_t number)
{
/* Primality is internally handled for 0, 1, 2, 3, and 4. */
if (number <= 4)
return;
/* All larger even numbers are internally handled. */
if (!(number & 1))
return;
/* Outside the sieve? */
if (number > sieve_max) {
fprintf(stderr, "not_prime(): %" PRIu64 " is outside the sieve!\n", number);
exit(EXIT_FAILURE);
}
{
const uint64_t half = number / 2;
const size_t w = half / ULONG_BITS;
const unsigned long m = 1uL << (half % ULONG_BITS);
/* Half is the bit index in sieve[].
half / ULONG_BITS is the word containing the bit
half % ULONG_BITS that needs to be set. */
sieve[w] |= m;
}
}
The sieve of Eratosthenes construction I shall leave to you; my intent is to only show how a relatively efficient (that is, balancing memory use and run time) sieve for odd positive integers can be created and managed, using dynamic memory management.
(Verifying that a simple Eratosthenes sieve finds all 455,052,511 primes less than 10,000,000,000 takes less than 90 seconds, and that it finds all 203,280,221 32-bit primes takes less than 30 seconds, on my laptop, using a single core, and the above functions. For higher ranges, it is better to use a windowed sieve. Note that prime counting functions do not consider 0 and 1 prime, unlike the above is_prime().)