Posts by Adak

I see your code makes comparisons with doubles - which is quite hazardous. Floating point numbers can't represent all values - they have to (very closely) approximate some of them.

The "cleanest" way to work with numbers that must be compared, is to use a multiplier, and then cast them to integers. So 100.68 would become 10068, for example. Do that RIGHT AWAY, with every float value. Then, for your output, cast it back to a double, and divide it by the same power of ten that you multiplied it by.

Another way, is to make your comparisons within a small range, instead of a fixed value. if double > 4.89 && double < 4.91 kind of logic.

If you google for "problem comparing floats", you'll find a lot more info on it.

I was able today to fix the compiler problem I had since day #1, with printing out the answers quickly - like the testing rig does it. My compiler uses a very small default buffer for stdout (the monitor in this case). It just had to be made larger to perform printing at a good speed.

YEAH!! ;)

Here's how I approach this problem:

1) sort the letters you have, lowest to highest. I always want the permutations to start with the lowest possible one, and work up to the highest one, and be in order. And have no repetitions.

2) You will work from right to left, making swaps. Frequently, you will resort the string. A good little sorter to use is insertion sort, because it's SO fast with small data items that are almost sorted anyway. WAY faster than even Quicksort at this.

3) Take an example, "abcd":

4321 number the columns of letters, from right to left
====
abcd in your mind. No code needed for this.

abcd - string is sorted, low to high
abdc - swap #1 with #2 letter
acbd - When the #2 letter, has reached #1 position, no more swaps with it are
possible. Increment the position you're swapping with, to #3, and swap #3
with #1. And resort the string, low to high, ONLY from the position BEHIND
#3. You're not sorting the whole string, just the letters BEHIND where
you swapped to.

acdb - And start again with #1, swapping it with #2

Tilt your head to the left, or draw a line between the letter c in the first swap, and now the letter b. You'll see a straight line of c's or b's, as the letter "walks" toward the #1 position …

My sieve code is strung out over a 8 projects by now - just trying too many options, too fast. I'm working on getting it back to something sane.

Be patient, it will happen - at least enough to pass that SPOJ challenge - can't promise anything beyond that.

And *Happy New Year*!

The biggest improvement in run-time is always found by choosing the right algorithm - the logical steps that will be used by the program, to find the answer.

Then there are optimizations beyond the algorithmic one's, which I'd call "machine and language" optimizations.

This program appears to need both of them. What is the program trying to do, exactly?
And what are your run-time requirements for it's time?

I saw this site much earlier in the thread here, but thought "oh, this is much more optimizations that we need for an SPOJ problem", and kept on going.

I'll revisit it and see what I can gleen from what he's doing. He's doing more than "the wheel", there.

Hey adak I just noticed you found the solution for this problem, I am still worried about this question but don't know how to convert sieve algo to segmented sieve..
Please help me how u did this problem..:-/

We have good news and bad news:

Good news:
Passed the challenge in good time (7.9 seconds).

Bad news:
The majority of the code was all from someone else, I just submitted it for him, and had to use my name, to do that.

The successful code did NOT perform at all well on my PC, taking 15 seconds - and this is one fast overclocked PC, not a slow test rig ==> an 850MHz server! (Just a reminder that my own code does this test in 2.6 seconds, on my PC, yet fails to finish in 10 seconds on the challenge testing PC.)

The testing rig uses the Linux compiler, and I use a Windows compiler (Pelles), and their compiler does a better job, with this code - and the effect is hugely magnified because of the repetitive nature of the program.

The program itself (the successful program), builds up an array of the answers first, and then uses fwrite() to output all the answers, in one single call.

When no one posted back into this thread for several weeks, I lost interest in the challenge. I don't want to post the actual code because it would make the challenge, useless.

…

Your program plays the puzzle, but it doesn't play it as smartly as it could. The puzzle is all about the first player taking the initiative, and keeping it. If player1 does that, he can always win the game.

If not, he can be made to lose, every time.

It's all about counting what's left for the opponent to use, after you make your play. Here's a winning strategy for player1:

Player 1  Coins Left   Player2  Coins Left
==========================================
1. take 2    8         take 1      7 
2  take 1    6         take 1      5
3. take 2    3         take Any #  *  (he can take 1 or 2, but not 3 coins)
4. take the last coin(s)

To win, player1 must always leave an even number of coins greater than 4, after his move, or three coins. Anything else, and player2 can win. That means to force a win, player1 must take 2 coins on his first move.

Player2 must try and play so player1 is left facing an even number of coins, greater than 4, or three coins. If player1 makes one error, he can force a win.

Your program plays the game, but it doesn't use strategy.

Line 14:
totalsquares is being calculated from an uninitialized variable. Declare totalsquares, and don't give it a value until AFTER the user has entered the Nsize value.

Line 20:
Same thing with calculating i and j - do that AFTER Nsize has been entered.

The malloc just seems wrong:

array = malloc(Nsize * sizeof(int*));
for(i = 0;i<Nsize;i++) 
   array[i]=malloc(Nsize * sizeof(int));

array[totalsquares] is never a part of the array. In C, array indices go from 0 to totalsquares - 1 only.

And I have no idea why you'd malloc an address to an int array[index], anyway.

It's always a good idea to free these malloc'd memory in their reverse order, just before your program ends.

A lot of schools use Turbo C because it is free, has a great help system, was easy to set up, and ran well in Windows, up through XP. It allowed the teacher and student, to focus on the C language, and not on the complexities of the IDE.

Turbo C does not promote void main() and never has, but after giving a warning when it's compiling, it will allow it, in accordance with the AT&T C standard that was in place, before the C language standard was created.

However, Windows 7 has no native support for 16 bit code, which is what Turbo C is. When you get to Windows 7, it is time to upgrade - for Windows only (and C only), a fine choice is Pelles C - it's free, has compatibility settings for old C names if you want it, and is C99 compliant, so it's right up to the very latest standard. All wrapped up with an easy to use Windows IDE (in both x32 and x64 bit capability).

Pelles even has it's own forum for answers to the most difficult questions regarding Pelles C.

With any Windows based IDE, you will have some added complexity. There's no way around that. The advantages however, of a modern C99 compiler, with full support for all the new headers, in both 32 and 64 bit versions, are compelling. Also, it has some extra nice features like showing you the matching braces, line numbers, …

This is the basic format type of code. (It's actually from another post on this forum). I like using fgets() to put a row of text into a char buffer array - just make sure it's plenty bigger than the longest possible row of input. Waste a little memory here, to keep everything working right.

I initialized the buffer here with digits, but you will use fgets() to put them into the buffer:

fgets(charArrayName, sizeof(ArrayName), filePointerName);

To read all rows in a data file, use:
while((fgets(charArrayName, sizeof(ArrayName), filePointerName))!= NULL) {
   //your code in here to handle the data
   //this reads all rows in the file, if the file is 
   //opened for reading

}

This is the program showing a few key idea's:

#include <stdio.h>

int main() { //
   int i,j,k,ok,n;
   int c2i[6][7];
   
   char buffer[128]={"0 0 1 0 1 1 0 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 0 1 1 0\n"};
   k=ok=0;
   for(i=0;i<6;i++) {                  //for every row
      for(j=0;j<7;j++) {               //for every column
         ok=sscanf(buffer+k, "%d",&n); //scan a char into n
         if(ok) {                      //we got one
            c2i[i][j] = n;             //into the integer array
            //printf("i: %d  k: %d, %d",i, k,c2i[i][j]); getchar();
            k+=2;                      //and increment an offset k
         }                             //for the next place to look for   
      }                                //the next digit.
   }
   //print each one, for an easy comparison check
   printf(" %s\n",buffer);
   for(i=0;i<6;i++)
      for(j=0;j<7;j++) 
         printf("%2d",c2i[i][j]);

   printf("\n");
   return 0; …

If the data is in a file,I'd use fgets() to get each row, then strstr() to look for GET in any row, and sscanf() to save it into the variable that you want.

Hey you can use turbo c in windows 7 by changing its compatibility..

I changed the following settings to make the window larger :

FONT >
Size = 28
Font = Consolas
LAYOUT >
Screen Buffer Size :
Width = 80
Height = 75

Window Size :
Width = 80
Height = 75

I'm a LONG time lover of Turbo C, but c'mon - it's days are over. Time to move on.

Coaching newbies on how to run their car or bike, on flat tires is not good! ;)

Pelles C is so easy and good for Windows C (32 or 64 bit), and no C++ junk in there.

You have read in a row of text from the file, with the code, into buffer (I used an array to avoid the file, for this example.)

This moves it from the buffer, as a string, into the int c2i[6][7] array.

#include <stdio.h>

int main() { //
   int i,j,k,ok,n;
   int c2i[6][7];
   
   char buffer[128]={"0 0 1 0 1 1 0 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 0 1 1 0\n"};
   k=ok=0;
   for(i=0;i<6;i++) {
      for(j=0;j<7;j++) {
         ok=sscanf(buffer+k, "%d",&n);
         if(ok) {
            c2i[i][j] = n; 
            //printf("i: %d  k: %d, %d",i, k,c2i[i][j]); getchar();
            k+=2;
         }
      
      }
   }
   printf(" %s\n",buffer);
   for(i=0;i<6;i++)
      for(j=0;j<7;j++) 
         printf("%2d",c2i[i][j]);

   printf("\n");
   return 0;
}

I'd recommend strongly that you re-configure the arrays for c2i. Use one array, set up like this:

int c2i[6][7]; //or whatever your sizes should be.

Now instead of hassling with different array names, you have it all together in one array, and can refer to each subarray through the index: c2i[0], or c2i[1], or c2i[2], etc. And use the columns for each part of the data, rather than the rows.

Say you had a string buffer, with your data, taken from a row of text in a text file:

char buffer[128]; //plenty of extra room is good here
FILE *fp;

fgets(buffer, 128, fp); //gets your data into a char string.

//Now we need to sscanf() using a for loop to put it into the right int array:
for(i=0;i<6;i++) {
   sscanf(buffer, etc., c2i[i]);
}

I'm not sure of the particulars of the format for this, but sscanf() is just like scanf(), except the source of the data, is only a string, instead of keyboard or a file.

I'll post back with the answer to this, in a bit.

Welcome to the forum, Kgal! ;)

Your last row in G[][] is missing a digit.

So you want to change the name of the array the data is going into, in the outer loop of the input?

for(each array) { //change array names with every loop
   for(each element to be scanned into this one array) {
   
   }
}

Is that what you want?

Using 1 row per vector, with 7 columns doesn't appeal to you?

So far, you haven't shown any of your own work - and copy and pasting the requirements of the project, certainly doesn't count as work on your project.

So we have no idea what you're stuck on.

Get started on your assignment, and when you get stuck on something, post up about the problem you're having. Be specific! "This doesn't work" on a post, just doesn't give us much to go on.

Use how you would do this work by hand (paper and pencil), and use the same patterns of work and logic, to design your pseudo code. Then use your pseudo code, to design your program. Work through an example or two or three, of a students grading by hand, and you'll see the pattern emerge. Look for it.

And post back when you get stumped on a problem that you can show some work on, and has specifics. General problems take up too much time to try and sort through.

It's quite easy actually. ;)

The key is, when you exceed the maximum of a data type SOMETHING is going to go haywire. When you exceed a positive integer, it might go negative (or do something else).

A simple while loop (or for loop) will get you "close". Just keeping multiplying a test number of that data type, by 2. When you are "close", you might want to get even closer by using a smaller number, say 1.4, etc.

But you have to find out what "haywire" is for your compiler, and recognize it, in your code. When I did this, I found I could go quite a ways past that limit in the header, before it went "bonkers", with the number.

Don't be put off by the huge size of the floating point range - you multiple by 2 and you'll be as far as you want to go with x 2, pretty quickly.

Mine went x2, for N times, then another loop took the number x 1.6, for N2 times, then a third loop took the number x 1.4, and finally addition was used to zero in the maximum value (which was well beyond the value in limits.h).

I don't want to spoil it by posting my code for it - it's a great exercise to build up your problem solving skills.

Try Pelles C (a free Windows only C only compiler), and you won't look back to Turbo C. There is a learning curve, but it's not bad at all. MUCH more capable.

Yeah, you're welcome, but you can quit acting so DAM surprised! ;)

Show your include headers, main() etc.

AND USE CODE TAGS around your code, or lots of people will not read through your code

The accuracy I doubt, but it fixes the compiler errors:

/* doesn't work, just removing some compiler errors */

#include <stdio.h>

//function prototypes
void read_code(char *julian_date);
void extract_julian(int *day1, int *year1,char *julian_date);

int main(){

char julian_date[8]; /* julian date consists of 7 characters - leave room for the '\0'*/
int day1=0;
int year1=0;

read_code(julian_date);
extract_julian(&day1,&year1,julian_date);

printf("this is day %d\n",day1);
printf("this is year %d\n",year1);
return 0;
}

void read_code(char *julian_date)/*this function is for input*/
{
printf("input the julian date.\n");
scanf("%s",julian_date);
}

void extract_julian(int *day1,int *year1,char *julian_date)/*this function extracts the numbers from the julian date*/
{
sscanf(julian_date,"%d",year1); /* makes the first 2 numbers equal to year*/
sscanf(&julian_date[4],"%d",day1); /*makes last 3 equal to date*/
}

(click on the [CODE] icon one time, and paste in the code)

Welcome to the forum, Roflspanker! ;)

I believe I see the problem, but let me set it up in my compiler.

Your code tags were perfect - except one [ char got skipped, somehow.

First, welcome to the forum, Rutwvu! ;)

If you need to do a merge sort, why entertain the idea of using a bubble sort? Please don't do that! USE MERGE SORT!

Bubble Sort is fine for < 100 things, but for anything else, it's just for entertainment unless the data is nearly in sorted order - then it's good (but Insertion sort is just as good, and considerably more capable, and Shell sort - which is Insertion sort using gaps, absolutely ROCKS, compared to either one).

There are four sorting algorithms that are TOP tier, for a large quantity of thing to be sorted**:

1) Quicksort - can be easily optimized with a call to Insertion sort for the small sub-arrays! VERY fast!

2) Merge Sort Uses more memory, but also very fast, and can be optimized extensively.

3) Heap Sort
4) Optimized Shell Sort

Not listed are variants like Intra Sort, which use both Quicksort and Heap Sort

Radix Sort might be added to the list, but it hasn't impressed me on the newer PC hardware. Might be just me.

** I mean ROCK the house sorting. If you don't use Quicksort or Merge Sort, you should have a good reason why you didn't.

I didn't fully understand your "100 numbers are left in each child..." part of the description, but in any case, it's up to YOU to get this assignment …

TC is DOS based, and in the version I'm familiar with (Turbo C/C++ 1.01), It supports only 8+3 char's length for a filename.

The cmd.exe command window supports longer filenames, but that's entirely separate from the TC program.

Have you thought about updating to the newer compiler? I now use Pelles C (it's free), and I love it. ;) (it's only C, and only for Windows (32 or 64 bit).

Lovely.

I used Turbo C with both C:\TC and C:\TC\BIN in the path (not a file, the directories).

Had no problems, but my shortcut on the desktop changed me to TC\BIN for all work in the IDE.

You may have other difficulties because Vista is more 32 bit, whereas I was using XP, but try putting both directories in the PATH, and re-booting. Be sure your path change is in the Windows environmental variables, and not the old DOS config.sys and autoexec.bat files. Windows has it's own (similar files), but you can use control panel >> system >> environmental variables, also.

You probably don't want to delete a record - shocking I know. Simply zero out the main key (perhaps an ID number which can never be zero), and the last name, first letter, to an end of string char: '\0'. (It's strlen() will be 0 in that case)

You actually would like to keep about 10-20% of your array empty, and available for new record data. When the array data is loaded, your program should simply count the number of valid records. If the empty records rises above 20-25%, then it can compress the database back to 10%, if space and/or run time performance, is critical - otherwise, don't worry about it.

Your print and display functions need the adjustment made to them, (an if statement), so they don't display any invalid records, that have been "deleted" in this manner.

As far as moving data, have you tried:

temp is a local struct (because you did prototype your struct above main() in global space right?)

Then just a simple swap may work:

temp = yourStruct[i];
structArray[i] = structArray[i+1];
structArray[i+1] = temp;

If you have objects that need to be allocated, the above swap won't work as is, so always test it well.

I wrote a sweet little program for you over on the other board:
http://cboard.cprogramming.com/c-programming/143397-large-reference-file.html#post1070790

Check the LAST post in the thread.

I couldn't just correct your program. You will LOVE the new one, though. ;)

1) Once the base file name is assigned, it finds the whole set of numbered files, like:

data1.txt
data2.txt

etc. If you want to extend the number of files, just enlarge the filename char array.

2) It uses a binary search to eliminate all duplicate strings.

3) It uses an index[] array to do the sorting, so no strings are ever moved.

4) It works in memory, as much as possible, so it's quick. This is not the absolute fastest way to handle the whole job, but it is quick.

(The fastest way to do this job would require more knowledge of the system it's running on, how the files are named, how much resources are available, and testing.)

5) It needs no "reference" file. Any file can be the starting file.

6) It needs smaller resources (much smaller), so no malloc or really large static arrays, are needed.

It handles the above data in the blink of an eye. Sweet! ;)

Filenames are char's, so fgets() is always one of the better choices:

fgets(charArrayName, sizeof(charArrayName), filePointerName);

It adds a newline onto the end of the string, but it can be readily removed if you don't want it there:

int len = strlen(charArrayName);
if(charArrayName[len-1]== '\n')
   charArrayName[len-1]='\0';  //overwrite the newline char by shortening the string

scanf() can be used in this case, but it's a lot more work, because of the '.' and filename extension after it.

Oh yes!

Nothing personal, but I really dislike your code:

1) It's int main(void) or int main(int argc, char *argv[]), never just main or void main.

And always with a return (usually zero) to signify success to the OS and you.

2) Your indentations are an affront to real estate on the monitor. 2 to 5 spaces is plenty per level of indentation. Your style will run you right off the row, with most real programs.

3) Your sort is an OMG! Bug city hotel. It's so long, and so error prone to work with, it's just incredible.

C should be CONCISE, (short, and to the point), not a Rube Goldberg deluxe creation. Simple and clear are secondary goals to accuracy, but important one's nevertheless.

A good sorter should be 5 to 30 lines, depending on what you choose, and what function is doing the swapping.

4) Your braces (opening and closing), should vertically line up on the same column. Yours are FAR offset.

5) Why is an add function, an output function in your comments? BTW, this is how your sorting should be - concise!
This function, I definitely LIKE! ;)

Your code is wonderfully playful, great creativity, but never show it to someone as something like working code you wrote. If you ever need to extend or modify it, after you've been away from it for awhile, you will see what a nightmare on Elm St. it …

There are two basic types of algorithms to solve Sudoku:

1) Brute force - relies on making guesses, and typically uses either backtracking or coloring. "Dancing Links" algorithm is especially elegant, imo.

2) Use human type reasoning methods which limit guessing

It is FAR easier to use brute force with backtracking, then anything else. With modern hardware, brute force is also a fast method, if you know how to maximize your code.

Either algorithm will need to check for Naked Singles/Forced Singles, where the value for a square can be determined directly by simple inspection. For instance, if a row has squares with 2 through 9, the remaining square must have a 1 for it's value - entirely forced. Any square with only one remaining possible value, is a Naked Single, and it's value should be assigned, immediately.

Many brute force solvers, are not entirely brute force - they use the most productive human like reasoning to discover the values of empty squares, and if that succeeds in solving the puzzle, then great. But if not, then they switch to a brute force approach, and find one or all of the remaining values.

Note that although the human reasoning will solve many puzzles, it will not solve them all. There is no known algorithm that will solve every puzzle, without some form of guessing.

For more info on this -- way more info, visit the Sudoku Programming Forum:
http://www.setbb.com/sudoku/index.php?mforum=sudoku

It's …

As NIGHTS has stated, you run a HUGE risk of crashing the static sized arrays, by overstepping their boundaries, AND there is a risk that you will crash the program because it has run out of stack space - that is a small space set aside by C, but it is NOT the major space available. That major space is available by using malloc() or calloc().

Another problem with your code is that you never check whether the file you requested to be opened, has in fact, been opened. fopen returns a NULL pointer if a file can't be opened, but you never check for that. That can also crash your program.

You might have opened too many files, at one time - I mean perhaps you kept opening files, and not always closing the previous files, and continued opening more files. On most compilers, C has a limit of 256 files being opened at any time: 0 to 255. (if the operating system will allow it, of course, each OS installation may have a different upper limit, depending on it's resources.)

I'll study your code for awhile, but it's very late, and I'm going to sleep, soon. Without a small sample of the data, it's probably not going to be productive.

Your code is very difficult to study because you have not indented it to show subordinate lines of code, as indented, like you should have.

In comparefiles() you open two files and never close either of them. For the reference file, you can pass the FILE * (pointer), as a parameter, and not continually open and close, open and close, the file. Just rewind() it when you need to start at the beginning of the file again. For all other files that are opened in a function, they should be closed before the function returns.

That depends on what the program does:

If it's running the auto pilot of the jet I'm on, I'd like it to work exactly correctly, thank you. ;)

Even when safety isn't an issue, just imagine the waste from having printing software that goofs up 50000 copies of a book that is being printed up, or metal that is being cut and formed, etc.

You might see it as efficient, but as an employer, I'd see it most efficient to show such a programmer, their pink slip, and the door out. Having a reputation as a poor quality software house, is not good for your business.

You will want to have three functions, imo: getInput(), main() to process the data, and printIt() to make your output.

Right now, I'd start with those three functions, and make a file with the data, which your program can read when it starts, saving you the time and effort of filling in the data, each time the program needs to be restarted. (During coding, that will happen many times.)

If you're not comfortable with using a file for this, then use arrays and variables to hold the data for you, in the program, while testing is on-going.Remove it after it's working correctly, and you need to write the actual input code the assignment wants.

Using two array's is recommended. One for the students name, and one for their marks. So students[0] will have all his marks in the columns of the marks[0][0], marks[0][1], marks[0][2], etc. The student row number in the string array of students, will correspond with that students marks in the marks array row number.

Get started on that - no one is going to do your assignment for you, I assure you. When you get stuck on something, post up your code with code tags around it, and let us know what the problem is.

The more specific your description is, the better the answers will probably be.

A good simple way to do this is to always use two nested for loops:

An outer for loop to control the row variable(s)
   and an inner for loop to control the printing on that one line currently being printed.

Think of it like you are always going to print a box, and the box is made up on each row, with spaces and *'s. There is a relationship between the row you're currently printing, and the number of starts that need to be printed. Also, the number of stars, and the number of spaces, equal the width of the box. That is true for every row, regardless.

You may now safely and full confidence, chuck your code in the dust bin, and promise me you will not try to use such as that again. ;) It's all about using loops. Otherwise, it's headache city!

I can't answer your query, but I know who can. ;)

In chess, they use(d) a recursive version of mini-max called alpha-beta (which is just mini-max with a few lines of code to improve it).

Then, along came multi-core processors, and everyone wanted their chess program to run "deep" in parallel search modes, to take advantage of the extra horsepower available. This required an iterative version of alpha-beta, iirc.

The chess experts yak it up here: www.talkchess.com and PLEASE don't mention anything about any clone of a chess program!! That is the sore spot on their hide, believe me.

After registration (which takes a few days sometimes), go to the programming sub forum.

Many of the regulars there are chess authors themselves, some are former world champion chess programmers - they really know their alpha beta algorithms (and how to argue about cloned chess programs).

Looks like you want a bitwise or |

Check out this tutorial and see if it doesn't get you started:
http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/BitOp/bitwise.html

It's still too slow to pass the SPOJ TDKPRIME test, but it's the fastest version I've had, so far. (2.1 seconds on my PC).

It checked out as accurate! ;)

Here's the screen shot of the sieve being marked, with an upper limit of 65, so it can be studied.

The number on the far left, is the number whose multiples are being marked as composite numbers. The composite numbers being marked are stretched out to the right hand side, on the row. 63 wrapped around, it's being marked as 3 X 21.

You can see there are NO even numbers now being marked - and that's a nice efficiency gain. You can also see the several numbers being marked twice - like the 35 I mentioned in the last post. (Since it is a multiple of 5 and a multiple of 7 also).

Check your sieve marking loops, and see how your program handles it. I thought since my loops made sense, were quick, and accurate, that they were optimal. They certainly were not!

Hey,

Remove the ampersand & from the scanf() line of code. Strings don't work with that, just numbers and stuff.

Your char arrays are very small. Remember that all strings need a space for the end of string marker: '\0', which scanf() will try and place onto the end of the string.

You can't flush your kitchen faucet, only the toilet will flush. fflush(stdin), is undefined. Use fflush() with OUTWARD streams, only, not INWARD streams like stdin.

use getchar(); to remove the last newline from the key buffer stream. It IS necessary, sometimes.

Sorry, Gnomelook. This isn't a short order homework helper site. Here, as on most programming forums, it's up to YOU to start your assignment or project. When and if you hit a snag, then post your code or pseudo code, and we'll try to help get you past it.

But we don't start your work, for you. You've been in the class, reading the book/manuals, and listening to the lecturer - we haven't. You should know what your teacher wants FAR better than we do.

So start out, then post up, and ask about whatever problem you're having.

And welcome to the forum, Gnomelook! ;)

So I'm thinking about how to design the next part of the "poor man's segmented Sieve of Eratosthenes" program, when I notice that every single darn one of the programs I see, all have a DIFFERENT top and bottom for loop, to mark the sieve.

OK, some programs are designed to print out every prime less than say, a million - and we're not doing that. They can use the square root rule for primes being <= the square root of the top number (a million in this example), and we can't use that method, since we need any prime requested, up to 86 Million. That is, THE PRIME, can be up to 86 million, that is NOT a top number to stop calculating the primes at.

Anyway, so I start printing up my Sieve array, after every time through the loop. Just what IS actually being marked?

And dammit! I've got a TON of useless EVEN numbers being marked as composite, even though the top loop deals only with odd numbers!! The bottom (nested) for loop, was happily wasting time marking out useless numbers!! FCOL!!

I'm still checking the total accuracy of the changes I made to remove that waste, but in preliminary testing:

1) it's 0.5 seconds faster (from 2.66 to 2.1 seconds), which is a healthy percent increase, and

2) it's accurate.

I'll post a screen shot of what I'm talking about after I get the accuracy confirmed.

I …

Can you draw arcs by modifying the algorithm? yes.

But you can't use the neat algorithmic trick of the circle drawing algorithm, to that same exent (all four quads at once).

Maybe define a midline and try using both sides of the distance from that midline.

I'm thinking of a midline which intersects the arc in the center, at 90°. Points on the arc (both sides), would share an equal distance from a point on the midline.

I haven't done this, it's just an idea.

With a nudge from Diwakar, I'm trying to implement a "poor man's" segmented Sieve of Eratosthenes. Since I did most of my beer drinking at home, not in a frat, that promises to bring us all to new heights of hilarity/despair and achievement. ;)

The implementations I've seen for it, as well as the descriptions, get my brain on overload. Anyway, the SORT is back in play, and this time it's the little QuickShort to the rescue:

void quickShort(int A[], int l, int u) {
  int i, m;
  if(l >= u) return;
  m = l;
  for(i = l+1; i<=u; i++) {
    if(A[i] < A[l])
      swap(A,++m, i);
  }
  swap(A, l, m);
  quickShort(A, l, m-1);
  quickShort(A, m+1, u);
}
//With some help from swap():

void swap(int A[], int l, int m) {     
  int temp;
  temp = A[l];
  A[l] = A[m];
  A[m] = temp;
}

If it's not fast enough, I'll replace it, but it saves a lot of room.

I won't be sorting the queries, I'll be sorting an index to the queries, so the queries will be kept in their original order, but I'll be able to look at them for processing, in sorted order.

Hopefully, the program can find the biggest gaps quickly, and set the sieve loop finder so it can "jump" ahead, when it reaches these larger gaps. I divided 86 Million by 50,000, and it's only 1,720. So we may have a lot of gaps, but not a lot of really big gaps.

Good to hear about your quest, Diwakar. ;)

I've been using this for my Sieve program:

for(i=3;i<86026253;i+=2){  //was < SieveSize
      if(!s[i]){
         ++pcnt; p[pcnt]=i; 
       for(j = i+i;j<86026253;j+=i)s[j] = 1;   //was < SieveSize
      }
   }
   for(i=4999800,j=0;i<5000000;i++) 
      p[i]=Top[j++];

pcnt is the counter for the primes, as they are found. p[pcnt] is where the value of the prime is stored. That loop is as optimized as I can make it. I have an array of the Top[] prime numbers, that cuts down on some of the sieve looping, but it has minimal to no impact because of the small size of the file limit. If I minus one from the VALUE, in the i < VALUE, the sieve will be incorrect. That's true for both the top and the inner nested for loop VALUE, as well.

I'm using the multiple number prints with every call to printf() (using fprintf(stderr, or stdout, helps).

Just for fun, I submitted one version where it printed \r, instead of \n at the end of every number (Carriage return, but no line feed). It ran in less than 2 seconds on my PC. Failed - you guessed it - Time limit exceeded!! Holy Moly!

I held onto the idea that computing all the primes in the range, because it happened so fast, was the way to go. I'm now quite satisfied that is NOT the way to go, because I've optimized everything in the place, the pots and pans - the dirty dishes, -- …

The idea in the last post I made, showed no improvement in the run time.

Next idea was to assign the top several prime numbers, directly into the primes[] array. Due to the source file size limitation for this Challenge, it was of no benefit, either.

Ho Hum - another fine idea, shot down! ;)

I'm stuck at 2.66 seconds (on my PC), which is too slow on the testing PC (max time is 10 seconds). (With a "normal" command window size with space for 24 vertical rows. Less rows, means shorter run time.)

Next idea is clearly a way to speed up the printing to the console. I believe I have finally exhausted every other idea, for the moment.

Not much new to report. I tweaked my program a bit. It runs in 2.62 seconds, but that number depends on the number of rows in the command window. A larger window takes longer to scroll up all those 50K numbers. This version was printing out 250 numbers with each call to printf(). Indeed, the entire program code has very few lines that AREN'T part of the print loop.

With a very small window (just a couple of rows), run times decrease to less than 1 second. Kind of fun to watch. ;)

Unfortunately, the testing rigs PIII cpu was not impressed when it ran it, so it declared "Time limit exceeded". Such a buzz killer, that testing rig. :(

I have one more speed up idea in mind. (I keep saying that, one more, just one more). This is it:

the kth numbers come in, and go into the query array - call it q[]. The prime numbers, as they are found by using the Sieve, go into the primes array, call it p[].

When I have all the primes, now I have to just print them out, but it has to be done in the order requested by the queries (that was the shortcoming of the sort idea, mentioned earlier in this thread).

To print with the right order, I have been using:
printf("%d\n%d\n",p[q-1],p[q[i+1]-1]); and so on.

Now, I'm going to change this printing to a more direct p1 type …

Interesting - I tried to run my program twice on Sphere Online Judge's website - both times it exceeded the time limit of 10 seconds.

Then I tried it twice on IDE One. Both times they reported it had a run-time error.

Which leaves me wondering what's going on with this? The program runs fine time after time, and it's run time is between 2.6 and 4.2 seconds, depending on the version of it.

So I went into the forum and read up on the testing hardware - They're PIII Xenon's!!

My compiler is modern (just updated this year), and naturally I have no idea of how to make a program compile correctly for PIII's! They're using gcc's compiler, which should be OK for the PIII, but I've never used the gcc compiler.

I'm not confident I can meet this challenge on a PIII based system.

I'm using Pelles C (it's free), and has it's own small forum for really good advice. It's only C, and only for Windows, 32 and 64 bit, and the IDE is more intuitive, imo.