9 Replies - 572 Views - Last Post: 28 January 2013 - 07:11 PM Rate Topic: -----

#1 STaylorY  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 19-January 13

Access Violation?

Posted 27 January 2013 - 11:27 PM

Hey guys, so I'm trying to write a program that will calculate all the primes in a number up to n using the Sieve of Eratostheneus algorithm. I've written the code, it compiles with no errors or warning. However, when I try to run it the program closes. After doing some debugging I found that the source of the problem is coming from a method call (i'll state which method later) and a message in Visual Studio 2012 pops up saying Access Violation. However, the method I'm calling is set to public so I don't really understand what's happening. Any guidance would be appreciated!

I believe the error is occuring within the int sieveEratosthenes(LList* p, int lstSize) function and it's specifically occuring at the node->setPrime(false); call.

//Class Declaration
class ListNode
{
friend class LList;

public:
	ListNode(int item = 0, bool pVal = false, ListNode* link=nullptr);
	int getItem() { return item_; }
	bool getPrime() { return prime_; }
	void setPrime(bool p) { prime_ = p; }
	ListNode* getNext() { return link_; }

private:
	int item_;
	bool prime_;
	ListNode *link_;
};

//function
int sieveEratosthenes(LList* p, int lstSize) 
{
	//locals
	ListNode* node;
	bool pTest = false;

	//Populate the List
	for(int j = 2; j < lstSize; j++) //Starts filling the list at 2
	{
		p->append(j, true); //Values are not considered prime until tested
		cout << j << " has been added to the list." << endl;
	}

	//Algorithm
	for(int i = 2; i < lstSize; i++)
	{
		node = p->_find(i - 2); //i - 2, sets position in list equal to value being evaluated
		pTest = node->getPrime();
		if(pTest) //if node value is prime
		{
			for(int j = 2 * i; j <= lstSize; j += i)
			{
				node = p->_find(j-2);
				node->setPrime(false);
			}
		}
	}

	return 0;
}




Is This A Good Question/Topic? 0
  • +

Replies To: Access Violation?

#2 andrewsw  Icon User is online

  • It's just been revoked!
  • member icon

Reputation: 3729
  • View blog
  • Posts: 13,019
  • Joined: 12-December 12

Re: Access Violation?

Posted 28 January 2013 - 02:15 AM

My initial impression is:

You are filling the list up to, but less than, lstSize:

for(int j = 2; j < lstSize; j++) //Starts filling the list at 2

but you are allowing the multiples to reach lstSize itself:

for(int j = 2 * i; j <= lstSize; j += i)

Was This Post Helpful? 1
  • +
  • -

#3 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3648
  • View blog
  • Posts: 11,416
  • Joined: 05-May 12

Re: Access Violation?

Posted 28 January 2013 - 06:10 AM

The access violation is with regards to accessing memory that you don't own, not with regards to C++ accessibility. As noted by andrewsw, you are going past the end of your array and so trying to access memory that you don't own because it is likely that p[listSize] doesn't contain a valid pointer.
Was This Post Helpful? 0
  • +
  • -

#4 STaylorY  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 19-January 13

Re: Access Violation?

Posted 28 January 2013 - 08:24 AM

Thanks guys, that was the problem!
Was This Post Helpful? 0
  • +
  • -

#5 STaylorY  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 19-January 13

Re: Access Violation?

Posted 28 January 2013 - 04:11 PM

Hey guys, so I'm trying to write a program that will compute all of the prime numbers less than n. The code compiles with no errors or warnings, but when I run it I'm not getting the correct output. It's not showing the correct numbers as prime etc. Can anyone help me find out what's going on? I believe the source of my error is located within the trial() and sieve() methods. Thanks!

#include "timer.h"
#include <math.h>
#include <cstdlib>
#include <iostream>

using namespace std;


void trial(bool* aryPtr, int n);
void sieve(bool* aryPtr, int n);

int main()
{
    //Data
    bool* primeArray;
    int n, m;
    char t;
    Timer myTimer;

    //Get list size
    cout << "Please enter a positive integer, greater than 1: ";
    cin >> n;
    cout << endl;

    //Check for errors
    if( n < 0 || cin.fail() ) //Value is < 0 or not integer type
    {
        cout << "Invalid entry, exiting program." << endl;
        system("PAUSE");
        return 1;
    }

    //Determine method for evaluating primes
    cout << "Please select one of the methods below by entering ( 1 or 2 ): " << endl;
    cout << "1.) Trial Division [enter 1 for this option]" << endl;
    cout << "2.) Sieve of Eratosthenes [enter 2 for this option]" << endl << endl;
    cin >> m;

    //Check for errors
    if( m != 1 && m != 2)
    {
        cout << "Invalid entry, exiting program." << endl;
        system("PAUSE");
        return 1;
    }

    //Printing
    cout << "Would you like the list of primes less than " << n << " to be printed?" << endl;
    cout << "y for yes, n for no: ";
    cin >> t;

    //Check for errors
    if(t != 'y' && t != 'Y' && t != 'n' && t != 'N')
    {
        cout << "Invalid entry, exiting program." << endl;
        system("PAUSE");
        return 1;
    }

    //Evaluate Primes
	if(m == 1) //User specified trial division method
	{
		myTimer.Start();
		trial(primeArray, n);
		myTimer.Stop();
	}
	else if(m == 2) //User specified sieve method
	{
		myTimer.Start();
		sieve(primeArray, n);
		myTimer.Stop();
	}
	else //quit program if problem was encountered
	{
	    cout << "A problem occured, exiting program." << endl;
	    system("PAUSE");
	    return 1;
	}

	//Print List
	if(t == 'y' || t == 'Y')
	{
	    for(int i = 0; i < n; i++)
	    {
				cout << (i + 2) << " : " << primeArray[i] << endl;
	    }
	}

	//Print Timing
    if(m == 1)
    {
        cout << endl << "Evaluating, " << n << " integers using trial division, took approximately, " << myTimer.Seconds() << " seconds." << endl;
    }
    else if(m == 2)
    {
        cout << endl << "Evaluation, " << n << " integers using sieve method, took approximately, " << myTimer.Seconds() << " seconds." << endl;
    }

    //End program
    system("PAUSE");
    return 0;
}

void trial(bool* aryPtr, int n)
{
	//Allocate Array
	aryPtr = new bool [n];

    //prime flag
    bool pTest;

	//Populate the List
	for(int i = 0; i < n; i++)
	{
		aryPtr[i] = false; //Assume no number is prime until tested
	}

	//Overhead Loop, traverses through array index(s)
	for(int i = 2; i < n; i++)
    {
		pTest = true; //Assume number is prime until tested

		//Divide number by 2 to sqrt(i), i being the number tested
		for(int j = 2; j <= (int)sqrt(i); j++)
		{
			if( i % j == 0 && i != j) //If i/j has no remainder and i does not equal j, then # is not prime
				pTest = false;
		}

		//If pTest value has not changed then number is prime
		if(pTest == true)
		{
			aryPtr[i] = true;
		}
	}
}

void sieve(bool* aryPtr, int n)
{
	//Allocate Array
	aryPtr = new bool [n];

	//Populate the List
	for(int i = 0; i < n; i++) //n - 2, since 0 and 1 are not considered prime, "aryPtr[0] == 2"
	{
		aryPtr[i] = true; //Assume every number is prime until tested
	}

	//Overhead loop, traverses through array index(s)
	for(int i = 2; i < n; i++)
	{
		if(aryPtr[i] == true) //if node value is prime
		{
			for(int j = 2 * i; j < n; j += i)
			{
			    aryPtr[(j - 2)] = false;
			}
		}
	}
}


Was This Post Helpful? 0
  • +
  • -

#6 STaylorY  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 19-January 13

Re: Access Violation?

Posted 28 January 2013 - 04:50 PM

Hey guys, so I'm trying to write a program that will implement two algorithms for finding the prime numbers less than n. N being specified by the user. My code compiles with no errors or warnings, but when I run it, it's not accurately pointing out prime numbers, could anyone help me with this? Thanks!

#include "timer.h"
#include <math.h>
#include <cstdlib>
#include <iostream>

using namespace std;


void trial(bool* aryPtr, int n);
void sieve(bool* aryPtr, int n);

int main()
{
    //Data
    bool* primeArray;
    int n, m;
    char t;
    Timer myTimer;

    //Get list size
    cout << "Please enter a positive integer, greater than 1: ";
    cin >> n;
    cout << endl;

    //Check for errors
    if( n < 0 || cin.fail() ) //Value is < 0 or not integer type
    {
        cout << "Invalid entry, exiting program." << endl;
        system("PAUSE");
        return 1;
    }

    //Determine method for evaluating primes
    cout << "Please select one of the methods below by entering ( 1 or 2 ): " << endl;
    cout << "1.) Trial Division [enter 1 for this option]" << endl;
    cout << "2.) Sieve of Eratosthenes [enter 2 for this option]" << endl << endl;
    cin >> m;

    //Check for errors
    if( m != 1 && m != 2)
    {
        cout << "Invalid entry, exiting program." << endl;
        system("PAUSE");
        return 1;
    }

    //Printing
    cout << "Would you like the list of primes less than " << n << " to be printed?" << endl;
    cout << "y for yes, n for no: ";
    cin >> t;

    //Check for errors
    if(t != 'y' && t != 'Y' && t != 'n' && t != 'N')
    {
        cout << "Invalid entry, exiting program." << endl;
        system("PAUSE");
        return 1;
    }

    //Evaluate Primes
	if(m == 1) //User specified trial division method
	{
		myTimer.Start();
		trial(primeArray, n);
		myTimer.Stop();
	}
	else if(m == 2) //User specified sieve method
	{
		myTimer.Start();
		sieve(primeArray, n);
		myTimer.Stop();
	}
	else //quit program if problem was encountered
	{
	    cout << "A problem occured, exiting program." << endl;
	    system("PAUSE");
	    return 1;
	}

	//Print List
	if(t == 'y' || t == 'Y')
	{
	    for(int i = 0; i < n; i++)
	    {
				cout << (i + 2) << " : " << primeArray[i] << endl;
	    }
	}

	//Print Timing
    if(m == 1)
    {
        cout << endl << "Evaluating, " << n << " integers using trial division, took approximately, " << myTimer.Seconds() << " seconds." << endl;
    }
    else if(m == 2)
    {
        cout << endl << "Evaluation, " << n << " integers using sieve method, took approximately, " << myTimer.Seconds() << " seconds." << endl;
    }

    //End program
    system("PAUSE");
    return 0;
}

void trial(bool* aryPtr, int n)
{
	//Allocate Array
	aryPtr = new bool [n];

    //prime flag
    bool pTest;

	//Populate the List
	for(int i = 0; i < n; i++)
	{
		aryPtr[i] = false; //Assume no number is prime until tested
	}

	//Overhead Loop, traverses through array index(s)
	for(int i = 2; i < n; i++)
    {
		pTest = true; //Assume number is prime until tested

		//Divide number by 2 to sqrt(i), i being the number tested
		for(int j = 2; j <= (int)sqrt(i); j++)
		{
			if( i % j == 0 && i != j) //If i/j has no remainder and i does not equal j, then # is not prime
				pTest = false;
		}

		//If pTest value has not changed then number is prime
		if(pTest == true)
		{
			aryPtr[i] = true;
		}
	}
}

void sieve(bool* aryPtr, int n)
{
	//Allocate Array
	aryPtr = new bool [n];

	//Populate the List
	for(int i = 0; i < n; i++) //n - 2, since 0 and 1 are not considered prime, "aryPtr[0] == 2"
	{
		aryPtr[i] = true; //Assume every number is prime until tested
	}

	//Overhead loop, traverses through array index(s)
	for(int i = 2; i < n; i++)
	{
		if(aryPtr[i] == true) //if node value is prime
		{
			for(int j = 2 * i; j < n; j += i)
			{
			    aryPtr[(j - 2)] = false;
			}
		}
	}
}


Was This Post Helpful? 0
  • +
  • -

#7 undefined behaviour  Icon User is offline

  • New D.I.C Head

Reputation: 7
  • View blog
  • Posts: 36
  • Joined: 17-January 13

Re: Access Violation?

Posted 28 January 2013 - 05:29 PM

Do you know what "pass by value" means? When you pass primeArray to trial or seive, you're passing a copy of those objects. When you modify aryPtr from within those functions, you're modifying the copy; The original remains the same.

This means that your original primeArray remains uninitialised throughout the life of your program. Rather than passing primeArray by value, you'll want to pass it by reference, or pass &primeArray by value and modify *primeArray.

system("PAUSE"); is just silly, and I'm getting tired of explaining why. Don't use it. Use something specific and well defined, such as this pause():

void pause() {
    std::cout << "Press any key to continue." << std::endl;
    std::cin.putback(std::cin.get());
}

Was This Post Helpful? 1
  • +
  • -

#8 undefined behaviour  Icon User is offline

  • New D.I.C Head

Reputation: 7
  • View blog
  • Posts: 36
  • Joined: 17-January 13

Re: Access Violation?

Posted 28 January 2013 - 05:36 PM

I assume the problem in the original post is solved. Would a moderator be willing to close this one, since the author has duplicated his/her most recent request here?
Was This Post Helpful? 0
  • +
  • -

#9 Adak  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 331
  • View blog
  • Posts: 1,168
  • Joined: 01-April 11

Re: Access Violation?

Posted 28 January 2013 - 06:40 PM

Writing a program is a process. Start with the first function you will call from main(), and GET IT TO WORK -- THEN go to work on the next function. Compile frequently to test your syntax, but give it a test for accuracy before you go on to code the next function.

Let's look at the logic for a primeTester function (trial by division function).

You will need two local int's, and one parameter int. NOTHING ELSE.

parameter int: n //the number being tested to see if it's prime or not
int: i, limit //i is the loop iterator. limit is the highest value that needs to be tested

assign limit = (int)sqrt(n) + 1

Since this is trial by division, divisor higher than the square root of a number, will cause the value to become less, (think of testing 25. After the divisor reaches 5, any value <=25 as a numerator, when divided, will be smaller), not greater. This is the main idea of division - a bigger divisor, equals a smaller value.


You need one for loop, with i from 3 to < limit, with i incrementing by 2, each time through the loop. You will not be testing even numbers, since no even number after two, is a prime number ( and two is handled in main() ).


You need one if statement, inside the for loop:
if(n % i == 0) return 0

The for loop ends, and the last line of code is simply return 1, and the closing brace for the function. Any time the program reaches this point, the number is prime.

And that is all you need for a prime number tester function.

In main() you will handle 2 separately first, and thereafter, your loops will start at 3 and also increment by i+=2. Again, no even number can be a prime number, after 2. This way, you don't waste time testing them.


The call to the primeTester function will be from main(), roughly:
//you have max as the maximum number to be tested up to,
//from the user.

//you have already set up 2 as a prime number.
for(i=3;i<=max;i+=2) {
   if(primeTester(i)) {
      //i was prime, handle your array, or output to a file, 
      //the screen, etc., right here.
   }
}


The entire primeTester function is about 8 lines of code, depending on your style.
Was This Post Helpful? 1
  • +
  • -

#10 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3648
  • View blog
  • Posts: 11,416
  • Joined: 05-May 12

Re: Access Violation?

Posted 28 January 2013 - 07:11 PM

I merged the two topics together since the other thread was about the same general body of code.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1