I'm making a prime finder another thing I'd like is a loop to check all possible odd factors if I can do that i can find all primes under 18 quintillion I think and store them in files ( yes I have nearly 200 GB of space left). also thanks for the thread on finding position in a file it helped me stop the file getting to big too open in MS-DOS 98  6042 
You're kidding us right? Nobody in his/her right mind writes code like that. Have a look at this: -
#include <stdio.h>
-
-
static int isPrime(int n) {
-
-
int i, inc= 2;
-
-
if (n == 2 || n == 3) return 1;
-
if (n%2 == 0 || n%3 == 0) return 0;
-
-
for (i= 5; i*i <= n; i+= inc, inc= 6-inc)
-
if (!(n%i)) return 0;
-
-
return 1;
-
}
-
-
int main() {
-
-
int i;
-
-
for (i= 2; i < 10000; i++)
-
if (isPrime(i))
-
printf("%d\n");
-
-
return 0;
-
}
-
kind regards,
Jos
don't even understand that maybe that's why I never made it like that
Also Jos I'm looking for a loop to shorten it not a sidenote of how crazy i am
@scienceman88
I assume you're asking for a way to shorten the nest of if-statements. You could replace all of those if statements with a loop that starts at 3, increments by 2, and stops when the counter exceeds the square root of the number you're testing. That's not necessarily the best algorithm, but it is equivalent to the one you're using.
Banfa 9,065
Expert Mod 8TB
So you wouldn't call Jos loop rather shorter than your code then?
Banfa 9,065
Expert Mod 8TB
As an aside an alternitive to using a function to test to see if a number is prime if you are looking for primes in a given range of numbers is to just remove all the none primes from the list, something like -
Populate LIST will all integers from 2 to 18 Quintillion
-
-
LOOP
-
Get next NUMBER in list
-
Remove all multiples of NUMBER except NUMBER*1 from the list
-
UNTIL END IS REACHED
-
At the end of the algorithm you have a list that just contains prime numbers in the range you start with. I do not know how efficient this algorithm is but I believe it isn't too in-efficient.
To test for a number whether it's a prime or not is "undecidable," and in terms of time efficiency, I think it's NP-Hard; NP stands for None-polynomial.
Odd factors? I don't exactly got what you mean by this!
In the below discussion, I'm using the Dynamic Programming technique.
To shorten the loop you are writing,
1. start with the 2 and 3 as the prime numbers, by definition.
2-a. get the next prime number,
2-b. add to the list of sentinels
3. process: do what ever you want.
So, talking about step 2 above, an efficient, but none-optimized, algorithm is the following, here is the "basic" idea.
From now on, I'll be using RO to stand for "Room for Optimization," and OT for "Optimization Technique being used/adopted." -
/* define your list of sentinels, this BASIS list might change according to the OT. */
-
-
int sentinels[] = {2, 3} /* According to OT, 0 and 1 might be added */
-
int k = 2; /* the next avail slot in sentinels */
-
/* sentinels will be re-enlarged, re-allocate space using ralloc(), but less efficient to be re-allocated in the below function */
-
function is_prime(integral_type n)
-
{
-
/* k might be declared as static instead of being global above */
-
if (n in sentinels)
-
return TRUE;
-
/* compute the square root of n */
-
i = 3; /* RO */
-
r = floor(square_root(n)); /* RO */
-
while (i <= r && n % i) i++; /* Change of OT, then RO */
-
if ( i < r) /* premature */
-
return FALSE;
-
sentinels[k++] = n;
-
return TRUE;
-
}
-
Optimization fine point. The next available prime number is completely independent of the immediately preceding one and can never be used to test for the next available one. As thus, no room for optimization, but some improvement might be done -- no proof, ONLY ad hod -- for a specific problem domain, this sometimes works, but not absolute.
List of Sentinels. This list is incremental, need some specific point in the whole program as to be doubled in size, at some point this can't be done, due to the much wasted space, alternatively, some "predetermined" size, OT, can be added each time a space is needed.
Finding multiples of a prime and exclude them from testing.
Hope this helps out.
@scienceman88
To test if a particular candidate number is prime you need only check if any of the prime numbers less than or equal to the square root of the candidate are factors. Nothing is gained by checking for nonprime factors; nothing is gained by checking for factors greater than the square root of the candidate. However, the effort to distinguish prime factors from nonprime factors is not trivial.
If you step through Jos' code you will notice that the trickiness involving inc causes only factors that are not divisible by 2 or 3 (other than 2 and 3 themselves) to be checked against the candidate. That is, Jos prunes out a small subset of the nonprime factors in order to speed up the code.
You could try to prune out a larger subset of nonprime factors, but at some point the additional pruning overhead swamps the savings from skipping factors.
@hsheboul
The sentinels array is defined as having only two slots. The next prime added to the array (5) will be written past the end of the array -- wreaking havoc on the program. You either want to dynamically allocate sentinels and periodically realloc it or you want a large static allocation. For instance, if you know ahead of time that you intend to search for all primes less than N, you could define sentinels as follows (where Y = square root of N + 1; I'm too lazy to check if the +1 is actually needed): - int sentinels[Y] = {2,3};
Note: you have to compute Y yourself and type in the literal number; the compiler can't do it for you.
@donbock
You are right Don, I was not that precise in writing the pseudo code. @donbock
Ah, how large is that N, and how to find some info related to that N!
Two things can decide upon N:
(don't forget the problem is undecidable)
1. the hardware capabilities,
2. the time available
Check out http://primes.utm.edu/largest.html @scienceman88
Tadaa! Lines #10 and #11 are the loop you asked for. All primes (except 2 and 3) are a multiple of 6 plus or minus 1; that's exactly what that loop tests: i.e. if a number evenly divides by 6*x +- 1 it can never be a prime number.
kind regards,
Jos
Banfa 9,065
Expert Mod 8TB @JosAH
[slightly off topic silly and pedantic mode]Strictly speaking if a number is not a prime number it can "never" be a prime number there time is not a factor controlling if a number is prime or not :D
[/slightly off topic silly and pedantic mode]
Err Sorry
@Banfa
You're wrong: there can be temporary prime numbers; e.g. they can be prime during the weekends or after 11:00pm or so. My hypothesis is that every number can be a temporary prime number but we don't know when it'll be prime and maybe they're also shy so they won't show their primeness when they're prime ...
kind regards,
Jos ;-)
Okay
1)I barely understood your code jos
2)I tried to insert it to file instead and I couldn't get it to work.
3)N= max for unsigned long long integers or about 18,446,744,073,709,551,615
4) you can use prime numbers before to calculate the next one it follows the sieve of eratosthenes( i know the sieve of atkin is faster but I don't understand it) and those sieves are the only known ways to find all primes except maybe primality testing each number
5)I want to use ftell and f seek to keep the files small enough to read in dos 4GB(a little less for possible overflow) I think so
@scienceman88
1) Yes I know, I've always been a smartypants; my mother dropped me on my head when I was a baby ;-)
2) My code simply prints the primes to stdout; it doesn't take rocket science to print the primes to elsewehere.
3) I take your word for it; no, I won't I'll check it ... yep, you're right.
4) both are similar algorithms in disguise: sieves filter out equal factors for all numbers while my primality check filtes out all factors per number. It doesn't need that huge array of bits to keep track of all the numbers.
kind regards.
Jos
@scienceman88
Just keep track on the number of bytes written already; when it exceeds a certain threshold, close the file and quit the process. There's no need for ftell() or fseek().
kind regards,
Jos
@JosAH
unless I watch it manually close it and expect it to say next file there is as i know it won't all get into one file of 4 gb or less
I can't get it to print to file never worked in more than one function before so unless i have to declare the pointer globally but change it internally I'll never be able to use the code
@scienceman88
Think 'object based': the 'object' or 'module' takes care of the printing and keeps track of that threshold value; whenever the number of bytes written exceeds that value, close the file, open a next one and reset the number of bytes written. At the end close the last file.
kind regards,
Jos
I have no Idea how to josah
@scienceman88
That is not very a scientific attitude (despite the suggestion of your name). Can you come up with a function that returns a C string "file0", "file1", "file2" ... everytime you call it? If so you're halfway there ...
kind regards,
Jos
I have one in my original code but I can't even get the file part to work in your code so changing files is pointless also without fseek and ftell I don't know how to track the size of the file as for my name it's because I like science not people like you.
@scienceman88
Ok, I'll stop answering your questions then but mind you: nobody here is going to do your homework for you; we don't believe in that approach. You have to do your work and when you're stuck we can try to help you.
Bye bye.
Jos
@hsheboul
That test most certainly is a decidable problem. It may be a bit tough for large numbers but that's it. For any integral n > 0 I can decide in O(n) whether or not n is a prime number; it isn't even in any NP class of problems.
kind regards,
Jos
I'm not trying to sound mean but the best I've done in understanding you is the original code you posted that doesn't seem to allow a file pointer anywhere where it isn't global(and because it had no comments it took me 30 minutes( and a pasting into my compiler) to figure out as I've never made a program with more than one function) also nobody asked how long I've been using C I've been barely able to do anything and I've been at it less than a full 3 months only thing that helped me learn printing at all is codeguru.com and learning a bit about pointers ( obviously not enough) basically I want something like this:
if (i%x!=0 && x<=sqrt(i)){
x=x+2;
}
and if that shows to be false for all odd numbers under the sqrt(i) and the file size is not bigger than 4 gb then print it to primesx.txt and increase my primes variable by one.
@scienceman88
Here's a nice reference. Everywhere where I use printf() you can use fprintf() and use a file pointer (which you have opened somewhere before in your code). You have to learn how to crawl before you can walk; you have to learn how to walk before you can run ...
kind regards,
Jos
when i tried something as simple as this it fails as it goes above 25 the first square number greater than 3^2 that will be incountered if i=i+2 and i starts at 3
@JosAH
I only picked this name because I like science and crap_programmer and crappy programmer are already taken.
@scienceman88
OK. You started working with C less than 3 months ago. Let's get some further background. - Do you have a C mentor you can talk to face-to-face (teacher, fellow student, coworker)?
- How did you come up with the idea to find all primes that fit in a long long int?
- Do you have proficiency in any other computer languages or is C your first?
- Have you accomplished file I/O before this prime problem?
- Have you successfully used command line arguments (argv and argc)?
It sounds like file I/O is giving you the most trouble. Is that right? It sounds like you've reworked your program quite a bit to try to incorporate Jos' suggestion. It might help if you posted the current version and precsely described what is going wrong with it. Provide compiler and run-time error messages verbatim. If the program output is wrong, clearly describe how the actual output differs from the expected output.
@scienceman88
That is exactly what my isPrime() function does: it explicitly checks for the numbers 2 and 3 and then it loops over all numbers 6*x +/- 1; call that number 'i'; it loops for all 'i' where 'i*i <= n' or, as you put it: less than sqrt(n). My code simply avoids that sqrt( ... ) function call and it avoids spurious tests by simply checking for possible divisors of the form 6*x +/- 1.
There is no file fiddling in the isPrime() function, the printing is done outside of that function; they call that "separation of concerns" which is a good thing.
kind regards,
Jos
@scienceman88
I think of computer programming more as engineering than science. One of the primary strategies in engineering is decomposition, also called separation of concerns or divide-and-conquer. Break up the task into small enough subtasks such that each has a straightforward implementation and so that each can be tested in isolation.
I submit that the most important thing for you to learn while working out this prime problem is how to divide a computer program into functions.
How small should the subtasks be? To misquote Albert Einstein, "as small as necessary but no smaller".
What should be the relationships between the subtasks? Now you're getting into the realm of computer science. Refer to Coupling and Cohesion. As a neophyte you needn't get too worked up over these terms, but it is never too early to follow good engineering principles.
thank you josah I'm sorry I've never truely been diagnosed but since about ten years ago I've been told I might have autism which if I have done my research and understand it is a high iq social disorder that fits me as far as talking about subjects i like in conversation I like science get me on a science topic I know and you won't get me off it lol ( somewhat the same in math) maybe I'd do better talking binary lol.
I'm checking how big can fit into one file right now I've done vb.net before which I was helped into no I don't have a C mentor and most things I found until this site seem to be C++ or just don't seem to work for me. the idea came from when i tried to do it in vb.net. I'm not good but I have tried input and output a very small amount in C since I started learning in fact because I know it can be useful it was one of the first things i searched for outside basics. I've used system(); but not really argc or argv I've seen them in codes but know nothing about them.
well although I know of them I don't know much about the file input and output commands I only learned them from codeguru.com and after I learned pointer basics(which I'll need more of) they made a little more sense ( made more sense when i saw a code that instead of using const char* _blah blah I found code saying const *char _pathname
Ok, let's get on with the show: the chance of a number being prime is inversely proportional to the number of digits in that number, or roughly 1/log(n). Some sloppy math shows that for n numbers there are about n/log(n) primes. Substitute 2^64 for n and you get the number of primes that fit in a long long. On average a long long takes up about 19 digits so all your primes take 19*2^64/64 bytes (written in ASCII). That is way too much to store on disk.
kind regards,
Jos
is there a statement to change type of variable or do i have to use void if so I could change it's type as i go and save space that way
@scienceman88
Nope, even when you use just eight bytes per number you end up with 2^64/64 bytes (give or take a bit) which is also way too much to store on disk. It can't be really compressed because the distribution of primes is considered random. It just can't be done. You have to limit yourself to unsigned long; it can handle numbers in the range [0 ... 2^32-1] which is still quite a lot ...
Let's do the (sloppy) calculation again for unsigned long: it contains n/log(n) prime numbers so an unsigned long can contain 2^32/5 prime numbers; a long takes up about 8 or 9 digits on average so all the prime numbers take up something like 2^32/5*8 == 2^35/5 bytes of storage.
kind regards,
Jos
@scienceman88
A variable is declared/defined with a particular type. There is no way to change the type on the fly. Why would you want to do so?
It sounds like you think you can reduce the size of the output file(s) by altering the type of the prime candidate variable on the fly. The type of the prime candidate variable is irrelevant. The size of the output file is determined by what is written to it. Jos assumed you want to write the decimal-ASCII representation of each prime to the file (he estimated that the average number of digits across all lines in the file would be 19). If you want to reduce the size of the file you need to either store fewer values in it or encode each value in fewer bytes -- you can roughly cut the file size in half if you represent each prime value as an 8-byte binary value.
You might argue that smaller prime values can fit in fewer bytes. The problem with variable-length entries is that it will be much harder to recognize the dividing line between one value and another. There are ways to do this; but you will have to be particularly clever to come out ahead.
@donbock
That still doesn't cut it ;-) do the calculations: 8*2^64/64 == 2^64/8 == 2^61 is still way too much.
kind regards,
Jos ;-)
I have a lot of google groups could I ftp to them ? I could fit at least 70 GB there even if it is compressed and a further 200 GB on my hard drive and maybe even a further 3-4 on my portable drive before I run out of room I might need to run it on a 64 bit computer to go that high anybody up for the challenge ? I calculated that as a long long I can fit over 20 billion primes on my computer uncompressed in normal ASCII form which means up to 40 billion primes uncompressed in the binary form you say will cut the size in half
I suggest you first get your program to produce a list of all the prime numbers less than 100. That list is short enough for you to hand-check the results against a reference book to confirm the program works properly.
After that, I suggest you modify the upper limit and produce a list of all the prime numbers less than ULONG_MAX (see limits.h). You should spot-check a few values in your output and also in your reference book to gain confidence every output value is a prime and that all primes are in the output.
After that, you can continue to increase the upper limit if you wish in order to enter long long int territory.
Make sure that your program tests each file I/O call for failure.
I've went all the way to 1 million before I even posted or found this site
@scienceman88
Jos estimates 2^64/64 = 2^58 bytes of storage are needed if you use an 8-byte binary representation for each prime. A gigabyte is 2^30 bytes, so this is 2^28 = 268,435,456 Gigabytes of storage -- roughly a quarter million gigabytes!
You need to set your sights lower.
@scienceman88
You might want to repeat that feat using Jos' smaller algorithm. Your original source code has a huge number of equivalence partitions.
For example, a typo on line 182 (such as "969" instead of "967") would produce errors that wouldn't be seen in any prime numbers less than 1000.
Jos' algorithm has fewer equivalence partitions, so you have a higher degree of confidence in its output after verifying a relatively small sample.
@donbock
worked to 1000 at least so now it's just a matter of space and time.
yeah that actually was one of my fears before wikipedia has the first 500. I was thinking of encoding the numbers in base 32 (0-9 and a-t I think).that could save room as numbers under 1024 only need 2 bytes at most before the seperator, and the top numbers before they go weird would only need 13 bytes not 20 that it could take.actually what i found by experimenting in the beginning is that if you go over the limits it goes either negative numbers or positive numbers relative to the next possible division of numbers so you can go past 18 quintillion you might just have to figure out what they mean to decode them.
#include <stdio.h>
static int isPrime(int n) {
int i, inc= 2;
if (n == 2 || n == 3) return 1;
if (n%2 == 0 || n%3 == 0) return 0;
for (i= 5; i*i <= n; i+= inc, inc= 6-inc)
if (!(n%i)) return 0;
return 1;
}
int main() {
int i;
FILE *fp;
fp=fopen("sample.txt","w");
for (i= 3; i < 1000; i=i+2)
if (isPrime(i))
fprintf(fp,"%d,",i);
return 0;
}
@scienceman88
Suggestions: - Add a line betweeen 4 and 5 to return 0 if n<2. This insures that "1" and negative inputs are handled properly; that is, they are not considered prime.
- After line 15 you should trap an error if fp is NULL.
- After line 18 you should trap an error if fprintf returns a negative value.
- Before line 19 you should call fclose. You should trap an error if fclose returns a nonzero value.
"Trap an error" means print an error message to stderr and return a nonzero value from main. The standard function perror can help. Don't forget to call fclose on your way out from an fwrite error.
This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Philp Smith |
last post by:
Hi
Does anyone have suggested code for a compact, efficient, elegant, most of
all pythonic routine to produce a list of all the proper divisors of an
integer (given a list of prime...
|
by: Dave |
last post by:
I have to automate a process that assigns sales leads to sales people.
For example:
Every day we buy a list of sales leads, it ranges in size from 50 -
100 records.
We have a team of sales...
|
by: someone else |
last post by:
hi all
I'm a newbie to this group. my apologies if I break any rules.
I've wrote a simple program to find the first 1,000,000 primes, and to find
all primes within any range (up to 200 *...
|
by: gk245 |
last post by:
Trying to write a program that will figure out if a number is perfect
or not.
Here is my logic:
1) Read in the number
2) Split it up (number - 1)
3) Put all the split up numbers into an...
|
by: garyusenet |
last post by:
I'm trying to investigate the maximum size of different variable types.
I'm using INT as my starting variable for exploration. I know that the
maximum number that the int variable can take is:...
|
by: jknox13 |
last post by:
Hi,
I have to find the divisors of all numbers less than a number inputed by the user and state if a number is prime if no divisors. I have this code so far, but I'm getting the wrong output and...
|
by: Clint Boaz |
last post by:
I am just trying to learn C++ and having a problem trying to write a program that finds the sum of the proper divisors of a given integer n and returns whether n is deficient, perfect or abundant.
|
by: jimix |
last post by:
I have written the program for factors of #'s 1-50 but the factors print out below the number being factored. I can't figure out how to make it all on the same line.
i.e. (now) divisors of 25 are...
|
by: jmDesktop |
last post by:
From the Python.org tutorial:
.... for x in range(2, n):
.... if n % x == 0:
.... print n, 'equals', x, '*', n/x
.... break
.... else:
.... #...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
| |
